Complexity Theory

CSAIL members have done foundational work in computational complexity theory. Larry Stockmeyer, and Albert Meyer worked together to define the polynomial-time hierarchy in 1973. Michael Sipser's work has focused on circuit lower bounds, interactive proofs, and probabilistic computation. In addition, Silvio Micali and Shafi Goldwasser joint collaborations discovered zero-knowledge interactive proofs (with Rackoff) in the 1980's; followed by mutli-prover inteactive proofs and their connection to inapproximability of HP-hard problems. They both continue to work on the foundations of cryptography. 

As one of the discoverers of the PCP Theorem, Madu Sudan's work has led to the modern theory of inapproximability and he now works at the intersection of computational complexity and information theory. Ronitt Rubinfeld is one of the founders of the field of program checking and together with Sudan and Goldwasser in the field of property testing. Group member, Scott Aaronson is interested in quantum complexity theory and in barriers to solving P versus NP and related problems. While Dana Moshkovitz  has a broad interest in Theoretical Computer Science, with a focus on Probabilistically Checkable Proofs (PCP), Pseudo-randomness, Coding theory and Algorithms.


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.