Return to Colloquia & Seminar listing
Unique games and other 2-player, 1-round games
Algebra & Discrete Mathematics| Speaker: | Guy Kindler, Hebrew U in Jerusalem |
| Location: | Zoom lecture |
| Start time: | Thu, Dec 3 2020, 10:00AM |
The computer science of 2-player, 1-round games originates in the study of interactive proofs. In such a proof, two collaborative players, or provers, each receive a question from a referee chosen from a distribution. They must answer independently, and they win if they satisfy a predicate calculated by the referee. Their goal is to choose a strategy in advance that maximizes their chance of winning.
Calculating the maximal winning probability is computationally hard. The PCP theorem, which is one of the most influential CS theory results in recent decades, states that even roughly approximating the best chance of winning is NP-hard. One implication of the PCP theorem is that mathematical proofs, once properly formatted, can be statistically verified by only reading a few letters chosen at random. If the maximal value of a special called games called Unique Games is also hard to approximate, the impact would be profound. It would imply that one specific algorithm actually gives the best possible results for many computational optimization problems.
In this talk, I will describe some recent and not-so-recent advances in the study of 2-player, 1-round games. I will try not to rely on prior knowledge. Some works that I may mention include those of Boaz Barak, Irit Dinur, Pravesh Kothari, Subhash Khot, Dor Minzer, Muli Safra, David Steurer, Dana Moshkovitz, myself, and others.
All meetings this quarter will be by Zoom. Please see announcements or contact organizers for the passcode.
Stay afterwards for a brief, informal reception. Refreshments will be self-provided.