Many CSAIL members have done foundational work in complexity theory. Larry Stockmeyer and Albert R. 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 multi-prover interactive 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.
If you would like to contact us about our work, please scroll down to the people section and click on one of the group leads' people pages, where you can reach out to them directly.