The Theory of PCPs
Tuesday, November 3, 2026 - 4:15pm to 5:15pm
Refreshments:
at 4:00 PM
Location:
32-G449 (Kiva/Patil)
Speaker:
Dor Minzer
Biography:
https://sites.google.com/view/dorminzer/home
Seminar group:
I will discuss the theory of PCPs, from its inception in the early 1990's until the current state of affairs.
Our discussion will be centered around the field of hardness of approximation, and in particular explain how the Unique-Games Conjecture arose and the human work that has been done towards proving it over the years.
We will say a few words about OpenAI's recent resolution of the Unique-Games Conjecture.