
A Zero-Knowledge PCP Theorem
Nicholas Spooner, from Cornell University, presents a seminar talk at the Institute for Advanced Study on combining two landmark results in complexity theory: that every NP statement has a zero-knowledge proof, and that every NP statement has a probabilistically checkable proof (PCP) verifiable by reading only a constant number of positions. Spooner, working with Tom Gur and Jack O'Connor, shows how to achieve both properties at once, constructing polynomial-size proofs for NP languages that can be checked by querying O(1) positions while guaranteeing that querying any polynomial number of positions reveals nothing about the underlying witness. The talk walks through the construction and the proof techniques that make the zero-knowledge and local-checkability guarantees compatible. It assumes familiarity with PCPs, zero-knowledge proofs, and standard complexity-theoretic notation, and is pitched at researchers and graduate students working in theoretical computer science and cryptography.