BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1665
DTSTAMP:20260121T034650Z
SUMMARY:The PCP Theorem with a Single Composition
DESCRIPTION:Speaker: Amik Raj Behera (University of Copenhagen)\n\nAbstract
 : \nA Probabilistically Checkable Proof (PCPs) is a proof system with a pr
 obabilistic verifier that queries the given proof and either accepts or re
 jects. One would like to minimize the number of random bits and the number
  of queries made by the verifier. PCPs are a generalization of the complex
 ity class NP. In fact\, a celebrated result of Arora\, Lund\, Motwani\, Su
 dan\, Szegedy characterized NP by a PCP with O(log n) randomness and const
 ant queries\, which is known as the PCP Theorem.\nIn this work\, we give a
  new and a simpler proof of the PCP Theorem by constructing a class of PCP
 s with range of parameters which was not known before. To achieve this\, w
 e introduce "Zero-on-Variety Test"\, which acts as an alternative to sum-c
 heck protocols. Finally\, to get a PCP of our choice of parameters\, we ap
 ply the Zero-on-Variety test on subsets related to Boolean slices. Our new
  protocols build on ideas from the theory of Gröbner bases.\nThis is base
 d on a joint work with Prashanth Amireddy\, Srikanth Srinivasan\, Madhu Su
 dan\, and Sophus Valentin Willumsgaard\, and can be found here: https://e
 ccc.weizmann.ac.il/report/2025/165/\nShort Bio :  Amik Raj Behera is a Ph
 .D. student at the University of Copenhagen under the guidance of Prof. Sr
 ikanth Srinivasan. He did his master's at Aarhus University and bachelor's
  at the Chennai Mathematical Institute. His research interests are in comp
 lexity theory\, coding theory\, and problems with an algebraic flavor.\n
URL:https://www.tcs.tifr.res.in/web/events/1665
DTSTART;TZID=Asia/Kolkata:20260127T160000
DTEND;TZID=Asia/Kolkata:20260127T170000
LOCATION:via Zoom in A201
END:VEVENT
END:VCALENDAR