Theses most similar to Query-efficient checking of proofs and improved PCP characterizations of NP (Guruswami, Venkatesan, 1976-; 1999) read it

Efficient holographic proofs

Russell, Alexander Craig (1996)

  • Advisor: Michael Sipser
  • Department of Mathematics
Read it

Proof-carrying data

Chiesa, Alessandro (2010)

  • Advisors: Eran Tromer; Ronald L. Rivest
  • Department of Electrical Engineering and Computer Science
Read it

Symmetries in algebraic Property Testing

Grigorescu, Elena, Ph. D. (2010)

  • Advisor: Madhu Sudan
  • 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

Some closure features of locally testable affine-invariant properties

Guo, Alan Xinyu (2013)

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

Small PCPs with low query complexity

Harsha, Prahladh, 1976- (2000)

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

Frontiers in zero knowledge

Sahai, Amit, 1974- (2000)

  • Advisor: Shafi Goldwasser
  • Department of Electrical Engineering and Computer Science
Read it

Succinct non-Interactive arguments

Chiesa, Alessandro (2014)

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

LP/SDP hierarchy lower bounds for decoding random LDPC codes

Ghazi, Badih (2015)

  • Advisor: Madhu Sudan
  • 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