BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Memento EPFL//
BEGIN:VEVENT
SUMMARY:IC Colloquium : Lazy verification of proofs and hard problems
DTSTART:20121015T161500
DTEND:20121015T173000
DTSTAMP:20260501T023654Z
UID:e172144d106816c3d9c254337119df525499396e9e6163f44cdc6b9b
CATEGORIES:Conferences - Seminars
DESCRIPTION:Johan Håstad\, KTH Royal Institute of Technology\nAbstract\nV
 erifying a proof is often a tedious task requiring the verifier to read th
 e entire proof and check each step. In this talk we discuss Probabilistica
 lly Checkable Proofs (PCPs) which can be verified by random spot-checks lo
 oking at very small parts of the proof\, rejecting any proof of an incorre
 ct statement with good probability.\n\nIn some situations it is possible t
 o only read three (or even sometimes two) bits of the proof and still only
  be fooled to accept a proof for an incorrect statement with probability a
 bout one half. The purpose of the talk is to give a high level discussion 
 of the existence of such proofs. These results turn out to have surprising
  implications for the approximability of some NP-hard optimization problem
 s and some of these implications will also be described.\n\n\nBiography\nP
 rofessor Johan Håstad is the director of the Theory group in the School o
 f Computer Science and Communication at the KTH Royal Institute of Technol
 ogy.  He is a member of the Royal Swedish Academy of Science.  He receiv
 ed his BS in Mathematics at Stockholm University\, and his MS in Mathemati
 cs at Uppsala University.  A graduate of the Massachusetts Institute of T
 echnology with a Ph.D. in Mathematics\, he won the ACM Doctoral Dissertati
 on Award in 1986\, the Gödel prize for "Håstad's switching lemma" in 199
 4\, and his second Gödel prize for his groundbreaking work on inapproxima
 bility results in 2011.
LOCATION:BC 420 https://plan.epfl.ch/?room==BC%20420
STATUS:CONFIRMED
END:VEVENT
END:VCALENDAR