Our interests span quantum complexity theory, barriers to solving P versus NP, theoretical computer science with a focus on probabilistically checkable proofs (PCP), pseudo-randomness, coding theory, and algorithms.

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.

Research Areas

Impact Areas