- This event has passed.
CIS Seminar: “Efficient Probabilistically Checkable Proofs from High-Dimensional Expanders”
February 18 at 3:30 PM - 4:30 PM
In this talk, I will cover some exciting progress on constructing efficient PCPs. My work gives a systematic way to construct PCPs, improving upon the state-of-the-art PCP constructions from nearly 20 years ago. This implies that many well-known approximation algorithms are nearly-optimal under well-believed complexity-theoretic conjectures. In the process, we also solve various conjectures in property testing and distributed computing. These advances are facilitated by the newly-emerging theory of high-dimensional expansion and draw upon connections with various areas of theoretical computer science and mathematics.
Mitali Bafna
Mathematics, MIT
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 the complexity of combinatorial optimization problems, high-dimensional expanders and sum of squares algorithms.