Theses most similar to Some closure features of locally testable affine-invariant properties (Guo, Alan Xinyu; 2013) read it

Relativization of the theory of computational complexity.

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

  • Advisor: Albert Meyer
  • Department of Mathematics
Read it

Property testing : theory and applications

Raskhodnikova, Sofya, 1976- (2003)

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

Property testing for distributions on partially ordered sets

Biswal, Punyashloka (2007)

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

Matchings, matroids and submodular functions

Harvey, Nicholas James Alexander (2008)

  • Advisor: Michel Goemans
  • 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

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

Monotonicity testing

Raskhodnikova, Sofya, 1976- (1999)

  • Advisor: Michael Sipser
  • 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

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

Cumulative effects in quantum algorithms and quantum process tomography

Hess, Shelby Kimmel (2014)

  • Advisor: Edward Farhi
  • Department of Physics
Read it