definition

Unique Games Conjecture as an organizing hardness principle

The Unique Games Conjecture strengthens the PCP theorem by concerning a specific label cover instance type, and if true it would give a very simple optimal approximation algorithm across a huge class of problems, which is why it had such organizing power.

definitionpending

Speaker

Ankur Moitra

Evidence Quote

“if that version of a probabilistically checkable proof were true, it would have this great organizing effect where it would turn out that for a huge swath of problems, we would actually know what is the best approximation algorithm”

Source

Lex Fridman Podcast #503 - AI Crisis in Math— Lex Fridman Podcast
Created: 11/17/2026, 6:25:32 AM

Your notes

Loading notes...