Comment by winfieldchen

18 hours ago

> We prove the Unique Games Conjecture

The Unique Games Conjecture (sorry, "Unique Games Theorem" now!) is huge. It was a very significant pillar supporting many of the limits of the polynomial-time approximation algorithms in the graduate-level randomized and approximate algorithms course I took in theoretical computer science. Textbooks will have to be re-written.

Here is an explainer: https://share.gemini.google/nbjIK6X3tOfz

With UGC proved, certain polynomial-time approximation algorithms used in difficult real-life problems are now known to be the best approximations we can achieve in polynomial-time:

> If UGC holds, the elementary algorithm that grabs both ends of an edge is fundamentally the best efficient algorithm that will ever exist. No amount of advanced linear programming or heuristics can achieve a ratio of 1.999.

> Under UGC, the Goemans-Williamson algorithm's 0.87856 ratio is mathematically optimal.

> UGC is considered the "Rosetta Stone" of approximation algorithms. In 2008, Prasad Raghavendra proved that for every single constraint satisfaction problem (CSP), a canonical Semidefinite Programming relaxation paired with the best rounding scheme achieves the optimal approximation ratio if and only if UGC is true. If the conjecture holds, the algorithmic boundary for an entire class of combinatorial problems is completely resolved.

Other hardness of approximation results from this UGC proof:

> [Max acyclic subgraph, a problem encountered in real life]: No polynomial-time algorithm can fundamentally outperform an unthinking coin toss.

> [Relative scheduling, another realistic problem]: As with acyclic subgraphs, the problem is "approximation-resistant": clever algorithms cannot beat random shuffling.

4 comments

winfieldchen

Reply
jpcompartir  13 hours ago

Much of this goes way above my head, but I found it interesting nonetheless. Q I had was why textbooks would need to be re-written? From your account it doesn't seem like results are upended, but rather confirmed?

I suppose when people do re-write the textbooks they'll say "this is confirmed now" not "if this conjecture is true...", but usually re-writing the textbooks would imply that things have been shown to be false?

May have misunderstood. Thank you for the post though, it was very interesting to someone who doesn't know much about the topic.

  • emil-lp  13 hours ago

    I'm not the OP, but we usually don't build large theories on conjectures unless we have strong reason to believe they are true, such as P \neq NP, RH, etc.

    The resolution of UGC will lead to a new theory in approximation algorithms. Suddenly we can build on top of the results that previously said "unless UGC is false".

    But you're right in that the first step is simply to remove that last sentence from all the theorems.

shiandow  11 hours ago

In a way I'm not entirely sure if proving the conjecture or posing it is the most important part here. It used to not matter much because proving results dependent on a connecture and making progress towards solving it were considered mostly equivalent.

But the distinction is going to become relevant very soon if many conjectures can be resolved (albeit in inscrutable fashion) by throwing raw computational resources at it.