Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
This Computer Science/Discrete Mathematics Seminar presents a lecture on "A Zero-Knowledge PCP Theorem" delivered by Nicholas Spooner from Cornell University. Explore how two fundamental concepts in complexity theory—that everything provable is provable in zero knowledge (NP ⊆ CZK) and that everything provable is locally checkable (NP = PCP[log n, 1])—can be achieved simultaneously. Learn about groundbreaking research demonstrating that for every polynomial Q, every NP language has a polynomial-size proof that can be verified by querying only a constant number of positions, while ensuring that querying any Q(n) positions reveals no information about the witness. The seminar, based on joint work with Tom Gur and Jack O'Connor, offers insights into this significant advancement in modern complexity theory. The lecture takes place at Simonyi Hall 101 at the Institute for Advanced Study, with remote access also available.
