CMSA Colloquium: Recent Advances in Probabilistically Checkable Proofs

Name: CMSA Colloquium: Recent Advances in Probabilistically Checkable Proofs
Start: 2025-12-08T16:30:00-05:00
End: 2025-12-08T17:30:00-05:00
Location: CMSA, 20 Garden St, G10

CMSA COLLOQUIUM

When: December 8, 2025

4:30 pm - 5:30 pm

Where: CMSA, 20 Garden St, G10

Address: 20 Garden Street, Cambridge, MA 02138, United States

Speaker: Dor Minzer (MIT)

The PCP Theorem is a cornerstone of computer science, with applications to hardness of approximation, verification, interactive protocols and more.

It asserts a witness for the satisfiability of a given 3CNF formula can be encoded in a robust way that allows local checking.
In this talk we discuss recent developments in PCPs, and their connection with distributed protocols, high-dimensional expanders and discrete Fourier analysis.

Based on joint works with Kai Zhe Zheng, Mitali Bafna, Noam Lifshitz, Nikhil Vyas