alt Hacker NewsUnique Games Conjecture [0] is a seminal conjecture in Complexity Theory, and is an underlying assumption for many, many inapproximability results. A valid proof is a big deal!
[0] https://en.wikipedia.org/wiki/Unique_games_conjecture [1] https://github.com/openai/math/blob/main/preprints/The-Uniqu...
Replies
impossiblefork • yesterday at 10:59 PM
Yeah, that's one of the big things of TCS. I think I see that as bigger than that Millenium Prize problem.
gregdeon • yesterday at 11:11 PM
This was the biggest highlight for me as well. Astounding...
I also don't think there was general consensus on which way this would resolve prior to this (or is that a little out dated?) unlike some of the other major problem resolutions. I heard rumors that there would be a big result in TCS and speculation it would be UGC that or P neq PSPACE but I'm still a bit shocked.