First Big Steps Toward Proving the Unique Games Conjecture
Kevin Hong for Quanta Magazine
Introduction
A paper posted online in January takes theoretical computer scientists halfway toward proving one of the biggest conjectures in their field. The new study, when combined with three other recent papers, offers the first tangible progress toward proving the Unique Games Conjecture since it was proposed in 2002 by Subhash Khot, a computer scientist now at New York University.
Over the past decade and a half, the conjecture — which asks whether you can efficiently color networks in a certain way — has inspired discoveries in topics as diverse as the geometry of foams and the stability of election systems. And if the conjecture can be proved, its implications will reach far beyond network-coloring: It will establish what is the best algorithm for every problem in which you’re trying to satisfy as many as possible of a set of constraints — the rules in a sudoku puzzle, or the seating preferences of a collection of wedding guests, for instance.
“For a whole huge family of problems, their complexity is beautifully explained if the conjecture is true,” said Irit Dinur, a theoretical computer scientist at the Weizmann Institute of Science in Rehovot, Israel.
Yet until this recent round of papers, all attempts to prove the conjecture had fizzled out. Meanwhile, computer scientists had come up with tantalizing hints that the conjecture might in fact be false.
“Some people felt that it is only a matter of time until the conjecture is refuted,” said Dor Minzer, a graduate student at Tel Aviv University in Israel and a co-author, along with Khot and Muli Safra of Tel Aviv University, of the four new papers (they are joined on the two middle papers by Dinur and Guy Kindler of the Hebrew University of Jerusalem).
With the new work, the prevailing winds appear to have shifted. “This is very strong evidence that the Unique Games Conjecture is true,” said Boaz Barak, a theoretical computer scientist at Harvard University who had previously been one of the conjecture’s most vocal doubters. “It’s a very exciting piece of work.”
One Beautiful Explanation
When Khot formulated the Unique Games Conjecture as a graduate student, he had a specific goal in mind: to better understand the computational complexity of the “graph coloring” problem, in which the goal is to color the nodes of a network (or “vertices” of a “graph,” as mathematicians put it) so that no two connected vertices are the same color. Theoretical computer scientists already knew that for graphs that require three or more colors, the problem of finding a coloring that uses the fewest possible colors is “NP-hard,” meaning that it belongs to a giant collection of computational problems, all of which researchers believe are beyond the reach of any efficient algorithm. (You can always find a valid coloring simply by trying every possible way to color the vertices, but for large graphs that brute force algorithm is very inefficient.)
But what if your palette holds more colors than are strictly necessary? Perhaps you’re considering graphs that require four colors, but you have 100 colors at your disposal. Can you efficiently color these graphs using that wider palette? Khot suspected that the answer was still no, but he couldn’t prove it. “This was my dream, since essentially the first year of my Ph.D.,” he said.
Khot figured out that the key to solving this problem lay in understanding the complexity of another problem, in which the goal is again to color a graph, but now there are rules that tell you, whenever you color a vertex, what color you must use on each vertex connected to it. The rules in this Unique Games problem might not all be compatible with one another (like conflicting seating requests at a wedding), so the goal is to find a coloring that satisfies as many rules as possible. (The name Unique Games comes from an equivalent formulation of the problem in terms of games rather than graph coloring.)
At first glance, it might seem that if the rules on your graph are almost perfectly compatible — say there’s some coloring that satisfies 99 percent of them — then it shouldn’t be too hard to find a not-utterly-abysmal coloring that satisfies, say, 1 percent of the rules. But Khot suspected that in this setting, finding even a 1 percent coloring is so tricky that there’s no efficient algorithm that can accomplish it for every graph. And the problem remains hard, he conjectured, even if your graph can satisfy 99.9999 percent of its rules and you’d be content with a coloring that satisfies 0.0001 percent of them — or any other pair of percentages, no matter how far apart.
Lucy Reading-Ikkanda/Quanta Magazine
Khot’s motivation in formulating this conjecture was tightly tied to graph coloring. But as he and other theoretical computer scientists started studying the ramifications of the conjecture, they found that it encodes a massive amount of information about problems far removed from graph coloring. The conjecture “completely took on a life of its own,” Khot said.
In particular, in 2008, Prasad Raghavendra of the University of California, Berkeley showed that if the conjecture is true then a certain simple algorithm called semidefinite programming offers the best possible approximate solutions to all “constraint satisfaction” problems, in which you’re trying to satisfy as many of a set of rules as possible.
“A priori, you can think of algorithm design as something very creative, where for every problem you have to figure out a new and different algorithm,” Barak said. But Raghavendra’s result meant that if the Unique Games Conjecture is true, then for a host of different problems, no ingenuity is needed — semidefinite programming is the one-size-fits-all solution.
“In science and math in particular, this is the kind of thing you really love — to have one beautiful explanation for a lot of things,” Dinur said. “From that perspective, you really want this conjecture to be true.”
After Raghavendra’s result, theoretical computer scientists’ degree of faith in the Unique Games Conjecture “became all about whether we believe semidefinite programming is so powerful,” said Dana Moshkovitz, of the University of Texas at Austin. For many theoretical computer scientists, this seemed a dubious proposition.
Their skepticism was bolstered by two peculiarities of the Unique Games problem. For one thing, Khot’s conjecture posits that finding (say) 1 percent solutions to 99 percent-satisfiable graphs is hard for some graphs, but no one has been able to come up with any specific example that cannot be solved easily. This is in stark contrast to most other hard problems. For instance, when it comes to factoring whole numbers — a problem widely believed to have no efficient algorithm — it’s easy to come up with numbers that stump factoring algorithms, simply by multiplying together large primes.
And in 2010, Barak, together with Sanjeev Arora of Princeton University and David Steurer of the Swiss Federal Institute of Technology in Zürich, came up with a “subexponential” algorithm for some forms of the Unique Games problem.
Brute force approaches to computational problems tend to have “exponential” running times, such as 2n or 3n. For instance, if you want to color a graph with n vertices using 3 colors, there are 3n possible colorings to consider — far too many for any computer to check in a reasonable amount of time, even for fairly small values of n. In a subexponential algorithm, the exponent is smaller than n — for instance, it might be the square root of n — which means that the algorithm is significantly faster than the brute force approach, though not fast enough to be considered truly efficient (an honor computer scientists reserve for algorithms whose running time is a polynomial, such as n2 or n3).
After the subexponential algorithm for Unique Games came out, “I think the algorithms people thought, ‘Well, we’ll keep working and we’ll get an actually efficient algorithm,’” said Ryan O’Donnell, of Carnegie Mellon University in Pittsburgh. If that happened, the Unique Games Conjecture would be disproved.
O’Donnell recalls informally polling theoretical computer scientists about the conjecture over lunch at the International Congress of Mathematicians in Seoul in 2014, where Khot was being awarded the Rolf Nevanlinna Prize — one of the highest honors in computer science — in large part for his work on the Unique Games problem. When O’Donnell asked who thought the conjecture was true, only he and Khot raised their hands.
“I thought it was kind of funny how he was getting a prize for this conjecture, and a lot of people seem to think it’s false,” O’Donnell said.
Hard, but Easy?
The argument laid out in the four new papers (which also relies on an observation by Barak, Steurer and Pravesh Kothari of Princeton University, as well as an idea from Moshkovitz) doesn’t provide a full proof of the Unique Games Conjecture. Instead, it proves the “2-2 Games” Conjecture, an analogous conjecture in which every time you color a vertex, the coloring rules give you two choices, not one, for the color of each neighboring vertex.
But this progress is already enough to have changed Barak’s mind about the Unique Games Conjecture. “I don’t see why one of these conjectures should be true and the other one should be false,” he said.
And in a specific sense, the new proof brings researchers halfway toward proving the Unique Games Conjecture itself. There’s an easy way to turn a “2-2” graph into a Unique Games graph: Simply throw away one of the two color choices for each rule. Then, if you have a coloring that satisfies nearly 100 percent of the 2-2 rules, this same coloring will likely satisfy about 50 percent of the Unique Games rules you’ve built.
Because of this relationship, it’s not hard to extend the new “2-2” proof to show that in the Unique Games setting, if you consider all graphs that can be colored in a way that satisfies at least 49 percent of their coloring rules (or 49.9999, or any number below 50 percent), there’s no efficient algorithm that can always find a coloring that satisfies even 1 percent of the rules, or 0.0001 percent, or any other small number. In other words, the Unique Games Conjecture has been proved for graphs that satisfy nearly 50 percent of their rules, but not yet for graphs that satisfy nearly 100 percent of their rules.
With this new work, “I think the tide is turning to thinking, ‘Well, OK, I guess probably these [Unique Games] problems really are hard after all,’” O’Donnell said.
Some of the Unique Games cases that have now been proved to be hard are also ones over which the subexponential algorithm holds sway, and this confluence of hardness and (comparative) easiness is, for some researchers, one of the most startling aspects of the new work. Nearly all problems in computer science seem to fall into one of two categories: Either they have an efficient algorithm, or they have no algorithm that’s much better than the brute force approach. The new proof shows that some cases of the Unique Games problem fall in the gap between these two categories — and some researchers see it as the only natural problem for which this is known to be the case. “It is provably in this weird twilight zone,” O’Donnell said.
Perhaps most exciting for Khot, the proof of the 2-2 Games Conjecture is already sufficient to settle a slightly weakened version of the original problem he was so captivated by as a graduate student, about whether widening your color palette allows you to color graphs efficiently. (The answer, essentially, is no.) “I think it is fair to say that what I thought of as my dream since year one of my Ph.D. is now done,” Khot said.
Fittingly for a problem that emerged from the mind of a far-seeing graduate student, many of the most important ideas in the new papers have come from the graduate student on the team, Dor Minzer. “The guy is amazing,” Khot said. “Dor was really kind of the architect of the whole thing.”
Lucy Reading-Ikkanda/Quanta Magazine
Many graduate students might have felt too intimidated to tackle a famously thorny problem like the Unique Games Conjecture, but for Minzer, that wasn’t a consideration. “The way I was thinking about it was that I had a chance to think about a problem which I think is interesting, with two people that I really respect, and let’s see what happens,” he said.
The January paper, which forms the capstone of the multipaper proof of the 2-2 Games Conjecture, has not yet been thoroughly checked by the theoretical computer science community. But researchers such as Barak and Dinur feel confident that its general approach is correct. The most groundbreaking ideas in the proof appeared in one of the earlier papers, Barak said, and that one he has carefully checked.
The most recent paper “is a tour de force and very technical, but my sense is that ultimately it proves a conjecture that is very believable, using the tools … that are natural to do so, by authors that are experts in this area,” he wrote in an email. “I think the result is on pretty solid ground.”
The biggest innovation in the new papers — a connection between the Unique Games problem and “Grassmann graphs,” mathematical objects that encode intersections between high-dimensional spaces — is probably not powerful enough to conquer the full Unique Games Conjecture, researchers agreed. “But I think this increases the optimism that somebody might discover a path — that this problem [of proving the conjecture] is not so impossibly hard,” O’Donnell said.
The discovery of that new path may now just be years, not decades, away, some researchers predicted. “I’ve always thought that the Unique Games Conjecture is one of those problems that is not meant to last for a century, but will be solved at some point,” Barak said. “This is a promising approach to actually do it.”
Correction October 2, 2018: This article has been revised to more accurately describe the problem of finding a coloring that uses the fewest possible colors, for graphs that require three or more colors, as “NP-hard” rather than “NP-complete.”
