Theses most similar to Analyzing monotone space complexity via the switching network model (Potechin, Aaron H; 2015) read it

Solving graph connectivity problems on JAGs

Husbands, Parry (1994)

  • Advisor: Mauricio Karchmer
  • Department of Electrical Engineering and Computer Science
Read it

Digital signatures from probabilistically checkable proofs

Sidney, Raymond M. (Raymond Mark) (1995)

  • Advisor: Silvio Micali
  • Department of Mathematics
Read it

Incrementally verifiable computation or knowledge implies time/space efficiency

Valiant, Paul (Paul Andrew) (2007)

  • Advisor: Silvio Micali
  • Department of Electrical Engineering and Computer Science
Read it

Huge networks, tiny faulty nodes

Peserico, Enoch (Peserico Stecchini Negri de Salvi) (2007)

  • Advisor: Larry Rduolph
  • Department of Electrical Engineering and Computer Science
Read it

Faster generation of random spanning trees

Ma̧dry, Aleksander (2009)

  • Advisor: Jonathan A. Kelner
  • Department of Electrical Engineering and Computer Science
Read it

Average-case complexity of detecting cliques

Rossman, Benjamin (Benjamin E.) (2010)

  • Advisor: Madhu Sudan
  • Department of Electrical Engineering and Computer Science
Read it

Vertex sparsification and universal rounding algorithms

Moitra, Ankur (2011)

  • Advisor: F. Thomson Leighton
  • Department of Electrical Engineering and Computer Science
Read it

Testability of linear-invariant properties

Bhattacharyya, Arnab (2011)

  • Advisor: Ronitt Rubinfeld
  • Department of Electrical Engineering and Computer Science
Read it

On threshold models over finite networks

Adam, Elie M (2012)

  • Advisors: Munther A. Dahleh; Ozdaglar, Asuman E
  • Department of Electrical Engineering and Computer Science
Read it

PCPs for Arthur-Merlin games and communication protocols

Drucker, Andrew Donald (2010)

  • Advisor: Scott Aaronson
  • Department of Electrical Engineering and Computer Science
Read it