Theses most similar to Algorithms and lower bounds in finite automata size complexity (Kapoutsis, Christos, 1974-; 2006) read it

Relativization of the theory of computational complexity.

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

  • Advisor: Albert Meyer
  • Department of Mathematics
Read it

Restricted branching programs and hardware verification

Ponzio, Stephen J. (Stephen John) (1995)

  • Advisor: Maricio Karchmer
  • 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

Digital signatures from probabilistically checkable proofs

Sidney, Raymond M. (Raymond Mark) (1995)

  • Advisor: Silvio Micali
  • Department of Mathematics
Read it

Incorporating specialized theories into a general purpose theorem prover

Pogosyants, Anna (1995)

  • Advisor: Stephen J. Garland
  • Department of Electrical Engineering and Computer Science
Read it

Local Hamiltonians in quantum computation

Nagaj, Daniel (2008)

  • Advisor: Edward H. Farhi
  • Department of Physics
Read it

Quantum computation beyond the circuit model

Jordan, Stephen Paul (2008)

  • Advisor: Edward H. Farhi
  • Department of Physics
Read it

Observational complexity of character strings.

Seiferas, Joel I (1972)

  • Advisor: John J. Donovan
  • Department of Electrical Engineering
Read it

Uses of randomness in algorithms and protocols

Kilian, Joe (1989)

  • Advisors: David Shmoys; Shafi Goldwasser
  • Department of Mathematics
Read it