Recent Advances in Probabilistically Checkable Proofs
CMSA Room G10 CMSA, 20 Garden Street, Cambridge, MA, United StatesColloquium 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 […]