Unique Games on the Hypercube

Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan

TL;DR

This paper explores the "last frontier" of the Unique Games Conjecture (UGC): the Boolean hypercube. The authors prove that the standard Goemans-Williamson semidefinite program (SDP) fails to solve Unique Games on the hypercube by constructing a specific "integrality gap" instance, but they also offer a path forward, conjecturing that adding triangle inequalities to the SDP might finally crack the problem for this difficult graph structure.

What Problem Does This Paper Address?

The Unique Games Conjecture is one of the most important open questions in theoretical computer science. If true, it explains why many optimization problems (like Max-Cut or Vertex Cover) are so hard to approximate. If false, it means we might find surprisingly powerful new algorithms.

Most "hard" instances of Unique Games can be solved by modern spectral algorithms—algorithms that look at the eigenvalues of the graph. However, the Boolean hypercube is a notorious exception. Because of its specific expansion properties, spectral algorithms perform poorly on it. This paper asks: Is the hypercube truly a "hard" instance that supports the UGC, or can we find a specific type of Semidefinite Programming (SDP) that solves it?

Methods

The authors focus on a specific version of Unique Games called Max-2-LIN($\mathbb{Z}_2$), where you try to satisfy a system of linear equations with two variables per equation over a binary alphabet.

  1. Integrality Gap Construction: They build a mathematical "trap" for the standard Goemans-Williamson (GW) SDP. They start with a hypercube where all constraints are "equalities" and then strategically flip a small number of edges to "inequalities" along $\sqrt{d}$ directions (where $d$ is the dimension).
  2. Fourier Analysis: To prove that their construction actually fools the SDP, they use the Walsh-Fourier transform. They analyze the "influence" of the majority function to show that the SDP thinks it can satisfy many more constraints than is actually possible.
  3. Gap Preservation (Tensor Products): They introduce a "tensor product" operation for Max-2-LIN instances. This allows them to take a small gap instance and "blow it up" to a larger hypercube while maintaining the gap between the true optimal solution and the SDP's optimistic estimate.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets. Instead, it uses the Boolean Hypercube ($Q_d$) as its primary mathematical object and benchmark. The authors introduce a new family of synthetic instances, denoted as $\Delta(k, d)$, which serve as the new "hard" benchmark for SDP solvers on hypercube graphs.

Key Insights and Ideas

  • The SDP's Blind Spot: The standard GW SDP is "too optimistic." On the hypercube, it can find a high-value vector solution that doesn't correspond to any real binary assignment. The authors quantify this by showing a gap where the real optimum is $1 - \Omega(\epsilon)$ but the SDP claims $1 - O(\epsilon^{3/2})$.
  • The Power of Inconsistent Cycles: A "Unique Game" is unsatisfiable if it contains "inconsistent cycles" (loops of constraints that can't all be true). The authors realized that while the standard SDP misses these, the hypercube is actually packed with them.
  • Triangle Inequalities as a Shield: The "aha moment" is that by adding triangle inequalities (constraints that enforce basic geometric logic, like $dist(a,c) \leq dist(a,b) + dist(b,c)$), the SDP is forced to "see" these inconsistent cycles. This effectively "breaks" the gap instance they created.

Key Results

  • Main Theorem: For any sufficiently small $\epsilon$, there exists a Max-2-LIN instance on the hypercube where the true combinatorial optimum is $1 - \Omega(\epsilon)$, yet the standard GW SDP returns a value of $1 - O(\epsilon^{3/2})$. This proves the standard SDP is insufficient for the hypercube.
  • Breaking the Gap: The authors prove that their specific gap instance is solved nearly optimally once triangle inequalities are added to the SDP (the "GW+" algorithm).
  • Abundance of Certificates: They prove that their hard instance contains $\Omega(\frac{k}{d} \cdot |E|)$ edge-disjoint inconsistent cycles. In the world of optimization, these cycles act as a "certificate" of unsatisfiability that the strengthened SDP can use.

Limitations and Future Work

  • Alphabet Size: The current proof focuses on an alphabet size of 2 (binary). While the authors believe their results extend to larger alphabets ($k$ labels), they haven't provided a formal proof for the general case.
  • The Conjecture: The biggest piece of unfinished business is Conjecture 5.4. The authors suspect that any instance of Unique Games on a hypercube that is significantly unsatisfiable must contain many edge-disjoint inconsistent cycles. If this conjecture is true, it would mean that the GW+ SDP algorithm solves Unique Games on the hypercube in polynomial time, potentially moving us one step closer to refuting the UGC.

Summary updated

Abstract

In this paper, we investigate the validity of the Unique Games Conjecture when the constraint graph is the boolean hypercube. We construct an almost optimal integrality gap instance on the Hypercube for the Goemans-Williamson semidefinite program (SDP) for Max-2-LIN$(\mathbb{Z}_2)$. We conjecture that adding triangle inequalities to the SDP provides a polynomial time algorithm to solve Unique Games on the hypercube.
BibTeX
@article{agarwal2015unique,
  author = {Naman Agarwal and Guy Kindler and Alexandra Kolla and Luca Trevisan},
  title = {{Unique Games on the Hypercube}},
  journal = {Chic. J. Theor. Comput. Sci.},
  year = {2015},
  url = {https://openreview.net/forum?id=SG-GfMbFgc},
}

Loading related content...

Figure