LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
A Zero-Knowledge PCP Theorem
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

A Zero-Knowledge PCP Theorem

65 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

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.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 5 m
Compared with MathematicsShorter than 69%
Source channelInstitute for Advanced Study (YouTube)