Unique Games Conjecture: OpenAI’s Proof and the Approximation Ceiling
When an algorithm gives you a pretty good answer, the obvious next question is whether a cleverer algorithm could do better. Sometimes the obstacle is engineering. Sometimes it may be a mathematical ceiling. The Unique Games Conjecture sits at that boundary. OpenAI has published a manuscript claiming to prove it, alongside formalization materials describing the … Read more