BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/604
DTSTAMP:20230914T125931Z
SUMMARY:Probabilistically Checkable Proofs
DESCRIPTION:Speaker: Madhu Sudan (Microsoft Research\nNew England Cambridge
\nUnited States of America)\n\nAbstract: \nAbstract: As advances in mathem
atics continue at the current rate\, editors of mathematical journals incr
easingly face the challenge of reviewing increasingly long\, and often wro
ng\, ''proofs'' of classical conjectures. Often\, even when it is a good g
uess that a given submission is erroneous\, it takes excessive amounts of
effort on the editor/reviewer's part to find a specific error one can poin
t to. Most reviewers assume this is an inevitable consequence of the notio
n of verifying submissions\; and expect the complexity of the verification
procedure to grow with the length of the submission.\n\nIn this talk I wi
ll describe how research\, mostly in the 20th century\, has allowed us thi
nk about theorems and proofs formally\; and how this formal thinking has p
aved the way for radically easy ways of verifying proofs. In particular I
will introduce the "PCP" (for Probabilistically Checkable Proof) format of
writing proofs. This is a format that allows for perfectly valid proofs o
f correct theorems\, while any purported proof of an incorrect assertion w
ill be ``evidently wrong''\, so that a reviewer checking consistency of a
very parts of the proof (probabilistically) will detect an error. The ex
istence of PCPs may seem purely fictional but research since the 1990s has
shown how such PCPs do exist. In this talk I will explain the concept of
a PCP. After giving some some background on why theoretical computer scien
tists are interested in PCPs and theorems and proofs in general\, I will a
ttempt to give an idea of how such PCP formats\, and associated verificati
on methods are designed.\n\nBrief Bio: Prof. Madhu Sudan has been a Princi
pal Researcher at Microsoft Research New England since 2009. He received h
is B.Tech. in Computer Science and Engineering from IIT-Delhi in 1987 and
his Ph.D. from the University of California\, Berkeley\, in 1992. From 199
2 to 1997\, he was at the IBM Thomas J. Watson Research Center\, after whi
ch he moved to MIT as a faculty member in the Electrical Engineering and C
omputer Science (EECS) department and a member of their Computer Science a
nd Artificial Intelligence Laboratory (CSAIL). Sudan's current research in
terests lie in the interface of Computation and Communication\, and in par
ticular\, in the role of errors in this interface. He has made important c
ontributions to theoretical computer science in areas such as probabilisti
cally checkable proofs\, non-approximability of optimization problems\, li
st decoding\, and error‑correcting codes. During his distinguished caree
r\, he has won many awards\, including the ACM Distinguished Doctoral Diss
ertation (1993)\, the Godel Prize (2001)\, and the Rolf Nevanlinna Prize (
2002). He is a fellow of ACM and the American Mathematical Society. Prof
. Madhusudan was awarded the Infosys Prize in Mathematical Sciences in 2
014.\n-----------------------------------------\nInfosys Science Foundatio
n lecture by Prof. Madhu Sudan Principal Researcher\, Microsoft Research N
ew England\, and Adjunct Professor\, Electrical Engineering and Computer S
cience department\, and Computer Science and Artificial Intelligence Labor
atory\, MIT\, Cambridge.\n
URL:https://www.tcs.tifr.res.in/web/events/604
DTSTART;TZID=Asia/Kolkata:20150611T160000
DTEND;TZID=Asia/Kolkata:20150611T170000
LOCATION:AG-66 (Lecture Theatre)
END:VEVENT
END:VCALENDAR