Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Learn about a groundbreaking result in complexity theory that combines zero-knowledge proofs with probabilistically checkable proofs (PCPs) in this lecture by Nicholas Spooner from Cornell University. Discover how this work demonstrates that every NP language has a polynomial-size proof that can be verified by querying only a constant number of positions while maintaining zero-knowledge properties - meaning that querying any polynomial number of positions reveals no information about the underlying witness. Explore the theoretical foundations that merge two fundamental results: that everything provable can be done in zero knowledge (NP ⊆ CZK) and that everything provable is locally checkable (NP = PCP[log n, 1]). Understand the implications of achieving both properties simultaneously and examine the collaborative research conducted with Tom Gur and Jack O'Connor that establishes this zero-knowledge PCP theorem.
