Complexity Theory

Many CSAIL members have done foundational work in computational complexity theory. Larry Stockmeyer and Albert R. Meyer worked together to define the polynomial-time hierarchy in 1973. Michael Sipser's work (with Furst and Saxe) established the first super-polynomial lower bounds on bounded-depth circuits, and the first derandomization in complexity classes by showing that BPP lies in the polynomial hierarchy, along with work in interactive proofs and quantum computing. Silvio Micali and Shafi Goldwasser's joint collaborations discovered zero-knowledge interactive proofs (with Rackoff) in the 1980's, followed by multi-prover interactive proofs and their connection to inapproximability of NP-hard problems. Ronitt Rubinfeld is one of the founders of the field of program checking and (together with Goldwasser) the field of property testing. Piotr Indyk and Virginia Vassilevska-Williams have done pioneering work in the area of fine-grained complexity, classifying and relating core problems within P (such as edit distance and longest common subsequence) which seem unlikely to have much faster algorithms than those presently known. Ryan Williams' work in complexity theory includes time-space lower bounds and circuit lower bounds, along with the establishment of counterintuitive connections between these topics and algorithm design. Anand Natarajan’s research is in quantum complexity theory, and his work has shown the surprising power of quantum multiprover interactive proofs, with consequences for mathematical physics and pure mathematics. Dor Minzer works in the area of probabilistically checkable proofs and its relation to Fourier analysis over various discrete domains.

Faculty Members: 

Shafi Goldwasser

Dor Minzer

Anand Natarajan

Ronitt Rubinfeld

Michael Sipser

Virginia Vassilevska Williams

Ryan Williams

Please click here for information on the Theory of Computation Seminars.

If you want information on the Algorithms and Complexity Seminars click here. 

For information on MSR/MIT Theory Reading Group, please click here.