Loading Events

CIS Seminar: “Efficient Probabilistically Checkable Proofs from High-Dimensional Expanders”

February 18, 2025 at 3:30 PM - 4:30 PM
Details
Date: February 18, 2025
Time: 3:30 PM - 4:30 PM
  • Event Tags:
  • Organizer
    Computer and Information Science
    Phone: 215-898-8560
    Venue
    Amy Gutmann Hall, Room 414 3333 Chestnut Street
    Philadelphia
    19104
    Google Map
    The 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 cloud computing.

    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.