TCS+ talk: Wednesday, March 19, Tom Gur, University of Cambridge
Clement Canonne
Our next talk will take place this coming Wednesday, March 19th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 18:00 Central European Time, 17:00 UTC). Tom Gur from the University of Cambridge will speak about "A Zero-Knowledge PCP Theorem" (abstract below).
Looking ahead, after Tom Gur we will have talks by Or Zamir (April 9th, on optimal moment estimation) and Ryan Williams (April 23rd, on space/time tradeoffs), with a hiatus on April 2nd due to the FOCS deadline.
Please sign up on the online form at https://sites.google.com/view/tcsplus/welcome/next-tcs-talk if you wish to join the talk as an individual or a group. Registration is /not/ required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The link to the recording will also be posted on our website afterwards.)
Hoping to see you all there,
The organizers
-------------------------------
Speaker: Tom Gur (University of Cambridge)
Title: A Zero-Knowledge PCP Theorem
Abstract: We show that every language in NP admits a probabilistically checkable proof (PCP) of polynomial length, which can be verified by only reading O(1) bits while revealing no information other than the correctness of the statement. This can be viewed as a zero-knowledge version of the PCP theorem, resolving a problem that was open since the seminal work of Kilian, Petrank and Tardos (STOC 1997).
Based on STOC 2024 and STOC 2025 papers, joint with Jack O’Connor and Nicholas Spooner.