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.

This is exactly the point. I was disappointed that I had to scroll so far down the page until I saw the word "entropy." There is a deep connection between machine learning and encryption and compression in information theory. As Shannon demonstrated, the one-time pad's encrypted output is maximum entropy, and so would data compressed to the Shannon limit. Such an optimal compressor learns the underlying probability distribution of the data to represent it with the fewest bits possible, which is exactly the goal of machine learning. A trained ML model can be seen as a lossy compression of the training data. Autoencoding models make the link between ML and compression (and thus encryption) explicit.