Mitali Bafna – Efficient Probabilistically Checkable Proofs from High-Dimensional Expanders

Abstract:

The PCP theorem, proved in the 1990s, shows how any proof can be encoded into a format that enables verification by making only a constant number of queries into the encoded proof. This landmark result in computer science has far-reaching implications for approximation algorithms and succinct verification, and PCP-based techniques are now being leveraged in blockchains like Ethereum.

In this talk, I will cover some exciting progress on constructing efficient PCPs. My work builds a new set of techniques using high-dimensional expansion to construct PCPs that improve upon the state-of-the-art constructions from nearly 20 years ago. This implies that many approximation algorithms are nearly-optimal under well-believed complexity-theoretic conjectures. In the process, we also solve long-standing open problems in property testing and fault-tolerant network design.

Bio:

Mitali Bafna is a postdoc at the Department of Mathematics at MIT, who is broadly interested in theoretical computer science. She graduated from Harvard in 2022 advised by Prof. Madhu Sudan. Her research focuses on complexity theory and algorithms, specifically combinatorial optimization, high-dimensional expanders and sum-of-squares algorithms. Her work has been awarded the Best Paper Award at STOC, 2025 and she was a Siebel Scholar (class of 2022).

Details

• Date: Thursday, March 13
• Time: 11:00 am - 12:00 am
• Category: Special Seminar
• Location: Grier A (34-401A)

Host

• Yael Kalai
• Email: chadcoll@mit.edu