BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1684
DTSTAMP:20260210T084518Z
SUMMARY:Efficient PCPs from High-Dimensional Expanders
DESCRIPTION:Speaker: Mitali Bafna (University of Washington)\n\nAbstract: \
 nThe theory of probabilistically checkable proofs (PCPs) shows how to enco
 de a proof for any theorem into a format where the theorem's correctness c
 an be verified by making only a constant number of queries to the proof. T
 he PCP Theorem [ALMSS] is a fundamental result in computer science with fa
 r-reaching consequences in hardness of approximation\, cryptography\, and 
 blockchain technology. A PCP has two important parameters: 1) the size of 
 the encoding\, and 2) soundness\, which is the probability that the verifi
 er accepts an incorrect proof\, both of which we wish to minimize.\nIn 200
 5\, Dinur gave a surprisingly elementary and purely combinatorial proof of
  the PCP theorem that relies only on tools such as graph expansion\, while
  also giving the first construction of 2-query PCPs with quasi-linear size
  and constant soundness (close to 1). Our work improves upon Dinur's PCP a
 nd constructs 2-query\, quasi-linear size PCPs with arbitrarily small cons
 tant soundness\, using high-dimensional expanders (HDX). As a direct conse
 quence\, assuming the exponential time hypothesis\, we get that no approxi
 mation algorithm for 3-SAT can achieve an approximation ratio significantl
 y better than 7/8 in time 2^{n/polylog n}.\nIn this talk\, I will discuss 
 the main components of our PCP\, without assuming any familiarity with PCP
 s or HDX. This is based on joint works with Noam Lifshitz\, Dor Minzer\, N
 ikhil Vyas and Zhiwei Yun.\n \nShort Bio: \nMitali Bafna is a theoretica
 l computer scientist and an Assistant Professor in the Allen School of Com
 puter Science & Engineering at the University of Washington. Her research 
 explores complexity theory and algorithms\, particularly approximation alg
 orithms\, probabilistically checkable proofs\, and high-dimensional expand
 ers. \nShe received her undergraduate degree from IIT Madras and her Ph.D
 . in Computer Science from Harvard University in 2022\, advised by Prof. M
 adhu Sudan. After that\, she was a postdoc at CMU\, hosted by Professors A
 ayush Jain and Pravesh Kothari\, followed by a postdoc in the MIT Departme
 nt of Mathematics.\n \n \n
URL:https://www.tcs.tifr.res.in/web/events/1684
DTSTART;TZID=Asia/Kolkata:20260220T113000
DTEND;TZID=Asia/Kolkata:20260220T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR