BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Perfect Zero-Knowledge PCPs for #P - Jack O'Connor (University of 
 Cambridge)
DTSTART:20240514T130000Z
DTEND:20240514T140000Z
UID:TALK212338@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:A probabilistically checkable proof (PCP) is a proof which can
  be verified by inspecting a small (usually constant) number of symbols fr
 om the proof. PCPs are fundamental objects in complexity theory\, with dee
 p connections to hardness of approximation. Informally\, we say a PCP is z
 ero-knowledge if no polynomial time algorithm with oracle access to the pr
 oof can learn anything more than the validity of the proof. Zero-knowledge
  proofs have been hugely influential in both cryptography and complexity t
 heory.\n\nWe construct a perfect zero-knowledge PCP for the #P-complete la
 nguage #SAT. Our construction is the first construction of a perfect zero-
 knowledge PCP for a language (believed to be) outside BPP. We achieve this
  result unconditionally\, and don't require any cryptographic assumptions.
 \n\nOur construction relies on both algebraic and combinatorial techniques
 \, including a version of the Reed-Muller code augmented with subcube sums
  and the combinatorial nullstellensatz. No background in zero knowledge wi
 ll be assumed for the talk. (Joint work with Tom Gur and Nicholas Spooner:
  https://arxiv.org/abs/2403.11941)
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR