Upcoming Talks

Ist logo

Hardness of approximation: From the PCP theorem to the 2-to-2 games theorem

Date: Friday, November 29, 2019 16:00 - 17:00
Speaker: Subhash Khot (New York University)
Location: Raiffeisen Lecture Hall
Series: Institute colloquium
Host: Uli Wagner
Contact: Arinya Eller
Central building lecture hall
Image

Abstract:

Researchers firmly believe that no algorithm can efficiently compute optimal solutions 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 numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.

In this lecture, Subhash Khot will provide an overview of those connections. He will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computer scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. He will explain how all this fits into a 30-year research program starting with the foundational Probabilistically Checkable Proofs (PCP) Theorem and leading to the recent 2-to-2 Games Theorem.
 

Qr image
Download ICS Download invitation
Back to eventlist