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:20210123T202003Z
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\, IST Austria
ORGANIZER:arinya.eller@ist.ac.at
SUMMARY:Hardness of approximation: From the PCP theorem to the 2-to-2 games
theorem
URL:https://talks-calendar.app.ist.ac.at/events/1908
END:VEVENT
END:VCALENDAR