Theses most similar to those of author Guo, Alan Xinyu

Some closure features of locally testable affine-invariant properties (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

New error correcting codes from lifting (2015) read it

Robust PCPs of proximity and shorter PCPs

Harsha, Prahladh, 1976- (2004)

  • Advisor: Madhu Sudan
  • Department of Electrical Engineering and Computer Science
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

Advances in sparse signal recovery methods

Berinde, Radu (2009)

  • Advisor: Piotr Indyk
  • Department of Electrical Engineering and Computer Science
Read it

Sketching and streaming high-dimensional vectors

Nelson, Jelani (Jelani Osei) (2011)

  • Advisors: Erik D. Demaine; Piotr Indyk
  • 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

Beyond locality-sensitive hashing

Razenshteyn, Ilya (2014)

  • Advisor: Piotr Indyk
  • Department of Electrical Engineering and Computer Science
Read it

On Learning and Covering Structured Distributions

Kamath, Gautam (Gautam Chetan) (2014)

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

Exploiting chordal structure in systems of polynomial equations

Cifuentes Pardo, Diego Fernando (2014)

  • Advisor: Pablo Parrilo
  • Department of Electrical Engineering and Computer Science
Read it

Succinct garbled RAM from indistinguishablity obfuscation

Holmgren, Justin Lee (2015)

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