Colloquium Details
Efficient Probabilistically Checkable Proofs from High-Dimensional Expanders
Speaker: Mitali Bafna, Massachusetts Institute of Technology
Location: 60 Fifth Avenue 150
Date: February 26, 2025, 2 p.m.
Host: Nir BItansky
Synopsis:
The PCP theorem, proved in the 90’s, shows how to encode a proof for any theorem into a format where the theorem's correctness can be verified by making only a constant number of queries to the proof. This result is a significant milestone in computer science and has important implications for approximation algorithms, cryptography, and cloud computing.
In this talk, I will cover some exciting progress on constructing efficient PCPs. My work improves upon the state-of-the-art PCP constructions from nearly 20 years ago, by building a new set of techniques using high-dimensional expansion. 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 distributed computing.
Zoom: https://nyu.zoom.us/j/98734522228
Note: In-person attendance only available to those with active NYU ID cards.
Speaker Bio:
Mitali Bafna is a postdoc at MIT who is broadly interested in theoretical computer science. She was a postdoc at CMU from 2022-2023 and 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.