Theses most similar to those of author Valiant, Paul (Paul Andrew)

Incrementally verifiable computation or knowledge implies time/space efficiency (2007) read it

Towards constant bandwidth overhead integrity checking of untrusted data

Clarke, Dwaine E. (Dwaine Errol), 1976- (2005)

  • Advisor: Srinivas Devadas
  • Department of Electrical Engineering and Computer Science
Read it

Efficient holographic proofs

Russell, Alexander Craig (1996)

  • Advisor: Michael Sipser
  • Department of Mathematics
Read it

Études in non-interactive zero-knowledge

Shelat, Abhi (2005)

  • Advisor: Silvio Micali
  • 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

Security proofs for the MD6 hash function mode of operation

Crutchfield, Christopher Yale (2008)

  • Advisor: Ronald L. Rivest
  • Department of Electrical Engineering and Computer Science
Read it

Deterministic algorithms for the Lovász Local Lemma

Haeupler, Bernhard (2010)

  • Advisor: David R. Karger
  • Department of Electrical Engineering and Computer Science
Read it

A study of statistical zero-knowledge proofs

Vadhan, Salil Pravin, 1973- (1999)

  • Advisor: Shafi Goldwasser
  • Department of Mathematics
Read it

Succinct non-Interactive arguments

Chiesa, Alessandro (2014)

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

Software protection and simulation on oblivious RAMs

Ostrovsky, Rafail (1992)

  • Advisor: Silvio Micali
  • 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

Testing symmetric properties of distributions (2008) read it

Property testing : theory and applications

Raskhodnikova, Sofya, 1976- (2003)

  • Advisor: Michael Sipser
  • Department of Electrical Engineering and Computer Science
Read it

Space-time tradoffs for graph properties

Dodis, Yevgeniy, 1976- (1998)

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

Testing and learning Boolean functions

Matulef, Kevin Michael (2009)

  • Advisor: Ronitt Rubinfeld
  • Department of Mathematics
Read it

Analysis of weighted l̳₁-minimization for model based compressed sensing

Misra, Sidhant (2011)

  • Advisor: Dimitris Bertsimas Pablo A. Parrilo
  • Department of Electrical Engineering and Computer Science
Read it

Testing k-wise independent distributions

Xie, Nin (2012)

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

Query-efficient checking of proofs and improved PCP characterizations of NP

Guruswami, Venkatesan, 1976- (1999)

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

Trace reconstruction problem

Pacchiano, Aldo (2014)

  • Advisor: Constantinos Daskalakis
  • Department of Electrical Engineering and Computer Science
Read it

Testing shape restriction properties of probability distributions in a unified way

Gouleakis, Themistoklis (2015)

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

Learning and testing junta distributions over hypercubes

Aliakbarpour, Maryam (2015)

  • Advisor: Ronitt Rubinfeld
  • 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