BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:Europe/Vienna
BEGIN:DAYLIGHT
DTSTART:20200329T030000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=3
TZNAME:CEST
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20191027T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RRULE:FREQ=YEARLY;BYDAY=-1SU;BYMONTH=10
TZNAME:CET
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20260404T145221Z
UID:1575039600@ist.ac.at
DTSTART:20191129T160000
DTEND:20191129T170000
DESCRIPTION:Speaker: Subhash Khot\nhosted by Uli Wagner\nAbstract: Research
 ers firmly believe that no algorithm can efficiently compute optimal solut
 ions to computationally complex problems called NP-hard problems. For many
  NP-hard problems\, even computing an approximately optimal solution is NP
 -hard. This phenomenon\, known as the hardness of approximation\, has nume
 rous connections to proof checking\, optimization\, combinatorics\, discre
 te Fourier analysis\, and geometry.In this lecture\, Subhash Khot will pro
 vide an overview of those connections. He will address why graph coloring 
 is a computationally hard problem\, how it is possible to check a proof wi
 thout even looking at it\, why computer scientists love the majority vote\
 , and whether a shape exists that looks spherical as well as cubical. He w
 ill explain how all this fits into a 30-year research program starting wit
 h the foundational Probabilistically Checkable Proofs (PCP) Theorem and le
 ading to the recent 2-to-2 Games Theorem. 
LOCATION:Raiffeisen Lecture Hall\, ISTA
ORGANIZER:arinya.eller@ist.ac.at
SUMMARY:Subhash Khot: Hardness of approximation: From the PCP theorem to th
 e 2-to-2 games theorem
URL:https://talks-calendar.ista.ac.at/events/1908
END:VEVENT
END:VCALENDAR