Theses most similar to Robust PCPs of proximity and shorter PCPs (Harsha, Prahladh, 1976-; 2004) read it

Relativization of the theory of computational complexity.

Lynch, Nancy A. (Nancy Ann), 1948- (1972)

  • Advisor: Albert Meyer
  • Department of Mathematics
Read it

Efficient holographic proofs

Russell, Alexander Craig (1996)

  • Advisor: Michael Sipser
  • Department of Mathematics
Read it

Order computations in generic groups

Sutherland, Andrew V (2007)

  • Advisor: Michael F. Sipser
  • Department of Mathematics
Read it

The Gowers norm in the testing of Boolean functions

Chen, Victor Yen-Wen (2009)

  • Advisor: Madhu Sudan
  • Department of Mathematics
Read it

Studies in program obfuscation

Varia, Mayank (Mayank Harshad) (2010)

  • Advisor: Ran Canetti
  • Department of Mathematics
Read it

Testability of linear-invariant properties

Bhattacharyya, Arnab (2011)

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

Polynomial identity testing of read-once oblivious algebraic branching programs

Forbes, Michael Andrew (2014)

  • Advisors: Amir Shpilka; Scott Aaronson
  • Department of Electrical Engineering and Computer Science
Read it

Structure vs. hardness through the obfuscation lens

Degwekar, Akshay (Akshay Dhananjai) (2016)

  • Advisor: Vinod Vaikuntanathan
  • Department of Electrical Engineering and Computer Science
Read it

Lower bounds on the classical simulation of quantum circuits for quantum supremacy

Dalzell, Alexander M (2017)

  • Advisor: Aram W. Harrow
  • Department of Physics
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