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.
Shafi Goldwasser, MIT EECS, UC Berkeley, and Weizmann Institute of Science professor and CSAIL member, was recently awarded the 2023 Dijkstra Prize in Distributed Computing alongside a team of researchers for their work on “Completeness theorems for non-cryptographic fault-tolerant distributed computation.”
Last week CSAIL principal investigator Shafi Goldwasser spoke about cryptography and privacy as part of the annual congressional briefing of the American Mathematical Society (AMS) and the Mathematical Sciences Research Institute (MSRI).
