BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:Algorithms and Complexity Seminar
SUMMARY:Perfect Zero-Knowledge PCPs for #P - Jack O'Connor
(University of Cambridge)
DTSTART;TZID=Europe/London:20240514T140000
DTEND;TZID=Europe/London:20240514T150000
UID:TALK212338AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/212338
DESCRIPTION:A probabilistically checkable proof (PCP) is a pro
of which can be verified by inspecting a small (us
ually constant) number of symbols from the proof.
PCPs are fundamental objects in complexity theory\
, with deep connections to hardness of approximati
on. Informally\, we say a PCP is zero-knowledge if
no polynomial time algorithm with oracle access t
o the proof can learn anything more than the valid
ity of the proof. Zero-knowledge proofs have been
hugely influential in both cryptography and comple
xity theory.\n\nWe construct a perfect zero-knowle
dge PCP for the #P-complete language #SAT. Our con
struction is the first construction of a perfect z
ero-knowledge PCP for a language (believed to be)
outside BPP. We achieve this result unconditionall
y\, and don't require any cryptographic assumption
s.\n\nOur construction relies on both algebraic an
d combinatorial techniques\, including a version o
f the Reed-Muller code augmented with subcube sums
and the combinatorial nullstellensatz. No backgro
und in zero knowledge will be assumed for the talk
. (Joint work with Tom Gur and Nicholas Spooner: h
ttps://arxiv.org/abs/2403.11941)
LOCATION:Computer Laboratory\, William Gates Building\, Roo
m SS03
CONTACT:Tom Gur
END:VEVENT
END:VCALENDAR