Theses most similar to Relativization of the theory of computational complexity. (Lynch, Nancy A. (Nancy Ann), 1948-; 1972) 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

Automated termination proofs using Walther recursion

Wu, Alexander (1994)

  • Advisor: David A. McAllester
  • Department of Electrical Engineering and Computer Science
Read it

Efficient holographic proofs

Russell, Alexander Craig (1996)

  • Advisor: Michael Sipser
  • Department of Mathematics
Read it

Algorithms and lower bounds in finite automata size complexity

Kapoutsis, Christos, 1974- (2006)

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

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

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

Unimodal, log-concave and Pólya frequency sequences in combinatorics

Brenti, Francesco, 1960- (1988)

  • Advisor: Richard P. Stanley
  • Department of Mathematics
Read it

Contraction maps and applications to the analysis of iterative algorithms

Zampetakis, Emmanouil (2017)

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