LECTURES A GRATIS GLOBAL SERVICE
⌕ SEARCH GRATIS GLOBAL ↗
LECTURES
What is the Unique Games Conjecture?
SOURCE: YOUTUBE · NO TRACKING UNTIL YOU PRESS PLAY · TROUBLE PLAYING? WATCH AT THE SOURCE ↗

What is the Unique Games Conjecture?

69 MIN · EN · STATUS: [ STREAMING ]
RATE THIS
IAS

Irit Dinur of the Institute for Advanced Study gives an informal overview of the Unique Games Conjecture, a central open problem in theoretical computer science concerning probabilistically checkable proofs and the hardness of approximation. She traces the background of the field, explains why the conjecture matters for understanding which optimization problems resist efficient approximate solutions, and discusses a recent contribution to the problem that came out of an OpenAI research effort. The talk is pitched as a 'What is...?' style introduction, aimed at giving newcomers a sense of why the conjecture has resisted proof or disproof for decades and how it connects to broader questions in complexity theory. Delivered at IAS's Simonyi Hall, the lecture balances technical framing with accessible explanation of PCP theory and its stakes for computer science.

At a glance

Lecture facts

Runtime compared with the other 734 Mathematics lectures
Runtime1 h 9 m
Compared with MathematicsShorter than 53%
Source channelInstitute for Advanced Study (YouTube)