Unique Games on the Hypercube

Naman Agarwal, Guy Kindler, Alexandra Kolla, Luca Trevisan

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.

Introduction

The Unique Games Conjecture (UGC) is a central pillar of modern computational complexity, providing a framework to understand why many optimization problems—such as Max-Cut and Vertex Cover—are difficult to approximate. While many "hard" instances of Unique Games have been resolved using spectral algorithms that analyze the eigenvalues of the constraint graph, the Boolean hypercube has remained a notorious exception. Due to its specific expansion properties, standard spectral methods perform poorly on it, making it the "last frontier" for testing the UGC.

This research explores whether the hypercube truly supports the UGC as a hard instance, or if a more powerful class of algorithms can solve it. The authors specifically investigate the performance of Semidefinite Programming (SDP) on this structure.

The Max-2-LIN($\mathbb{Z}_2$) Problem and the Standard SDP

The study focuses on a version of Unique Games known as Max-2-LIN($\mathbb{Z}_2$), where the goal is to satisfy a system of linear equations over a binary alphabet with two variables per equation. The standard approach to this problem is the Goemans-Williamson (GW) SDP. However, the authors demonstrate that this SDP has a significant "blind spot" when applied to the hypercube.

Constructing the Integrality Gap

The authors construct a mathematical "trap" for the GW SDP, known as an integrality gap instance. They begin with a hypercube where all constraints are equalities and strategically flip a small number of edges to inequalities along $\sqrt{d}$ directions (where $d$ is the dimension). To prove this construction fools the SDP, they utilize:

  1. Fourier Analysis: Using the Walsh-Fourier transform, they analyze the "influence" of the majority function to show that the SDP perceives a much higher satisfaction rate than is combinatorially possible.
  2. Tensor Products: They introduce a tensor product operation for Max-2-LIN instances, allowing them to scale small gap instances into larger hypercube structures while maintaining the gap between the SDP's optimistic estimate and the true optimum.

Key Insights: Inconsistent Cycles and Triangle Inequalities

A critical insight of this work involves inconsistent cycles—loops of constraints that cannot be simultaneously satisfied. While the standard GW SDP fails to detect these cycles on the hypercube, the authors realized that the hypercube is densely packed with them.

By adding triangle inequalities to the SDP—constraints that enforce basic geometric logic, such as $dist(a,c) \leq dist(a,b) + dist(b,c)$—the solver is forced to recognize these inconsistent cycles. This strengthened algorithm, termed GW+, effectively "breaks" the gap instance, forcing the SDP to return a value much closer to the true combinatorial optimum.

Key Results

  • Main Theorem: The authors prove that 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 confirms that the standard SDP is insufficient for the hypercube.
  • Breaking the Gap: The authors demonstrate that their specific gap instance is solved nearly optimally once triangle inequalities are added to the SDP.
  • Abundance of Certificates: They prove that their hard instance contains $\Omega(\frac{k}{d} \cdot |E|)$ edge-disjoint inconsistent cycles. These cycles act as a "certificate" of unsatisfiability that the GW+ algorithm can utilize.

Limitations and Future Work

While the current proof focuses on a binary alphabet, the authors believe their results may extend to larger alphabets. The primary remaining challenge is Conjecture 5.4: the suspicion that any significantly unsatisfiable instance of Unique Games on a hypercube must contain many edge-disjoint inconsistent cycles. If this conjecture is true, it would imply that the GW+ SDP algorithm can solve Unique Games on the hypercube in polynomial time, potentially moving the field closer to refuting the Unique Games Conjecture.

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},
}
Figure