Complexity Theory Group (CTG)

Interests in the Complexity Theory Group 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.

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.