Colloquium

Speaker: Dor Minzer (MIT)

Title: Recent Advances in Probabilistically Checkable Proofs

Abstract: 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.