CIS Seminar: “Efficient Probabilistically Checkable Proofs from High-Dimensional Expanders”
Amy Gutmann Hall, Room 414 3333 Chestnut Street, Philadelphia, United StatesThe 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 […]