Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree

Boaz Barak, Ankur Moitra, Ryan O'Donnell, Prasad Raghavendra, Oded Regev, David Steurer, Luca Trevisan, Aravindan Vijayaraghavan, David Witmer, John Wright

Introduction

Constraint Satisfaction Problems (CSPs), such as Max-Cut or Max-SAT, are central to theoretical computer science. Given the NP-hardness of finding optimal solutions, research often focuses on approximation algorithms. A natural baseline is the "random assignment," which satisfies an expected fraction $\mu$ of constraints. While Håstad demonstrated that beating this baseline for problems like Max-3XOR is NP-hard in the general case, the situation changes when the problem's degree $D$—the maximum number of constraints per variable—is bounded.

Recent work by Farhi, Goldstone, and Gutmann (2014) introduced the Quantum Approximate Optimization Algorithm (QAOA), achieving an advantage of $\Omega(D^{-3/4})$ over the random baseline for Max-3XOR. This paper investigates whether classical algorithms can match or exceed this performance.

Algorithmic Framework: Fixed vs. Greedy

The authors propose a classical approach based on a "Fixed vs. Greedy" partitioning strategy. This method leverages the multilinear polynomial representation of CSPs and utilizes Fourier analysis of Boolean functions.

  1. Decoupling: Variables are partitioned into two sets: $F$ (Fixed) and $G$ (Greedy).
  2. Random Assignment: Variables in $F$ are assigned independent, uniform random bits.
  3. Greedy Rounding: Variables in $G$ are assigned values to maximize the satisfied constraints based on the fixed values in $F$.

The analysis relies on "hypercontractivity," a property of low-degree polynomials that ensures they deviate significantly from their mean. This deviation allows the greedy step to capture a meaningful advantage over the random baseline. For higher-order Max-$k$XOR problems, the authors further refine this with a randomized rounding scheme based on the extrema of Chebyshev polynomials.

Structural Properties and Triangle-Freeness

A critical aspect of the analysis is the local structure of the CSP instance, represented as a hypergraph where variables are vertices and constraints are hyperedges.

Structural dependencies in bounded-degree CSPs: (left) two constraints sharing multiple variables; (right) a triangle of constraints.

The authors identify "triangle-freeness" as a key property for general CSPs. In a triangle-free instance, constraints do not overlap in complex cycles (like the one shown in the right of Figure 1), ensuring that local greedy choices do not interfere destructively. This structural simplicity allows the algorithm to maintain a consistent advantage across the entire instance.

Key Results and Optimality

The paper establishes several significant bounds:

  • Max-$k$XOR: For any odd $k$, an efficient algorithm finds an assignment satisfying at least a $\frac{1}{2} + \Omega(1/\sqrt{D})$ fraction of constraints.
  • Triangle-Free CSPs: For arbitrary triangle-free CSPs, the algorithm satisfies at least $\mu + \Omega(1/\sqrt{D})$ constraints.
  • Optimality: The authors prove that the $\Omega(1/\sqrt{D})$ advantage is optimal for general bounded-degree instances using a Chernoff-bound argument on random $D$-regular graphs.

These results demonstrate that classical algorithms can achieve a better scaling factor ($\Omega(1/\sqrt{D})$) than the previous quantum state-of-the-art ($\Omega(D^{-3/4})$), suggesting that the perceived quantum advantage in these bounded-degree settings may be less significant than previously thought.

Conclusion

This work provides a constructive, algorithmic version of Fourier tail theorems for low-degree polynomials. While the current results for general CSPs require triangle-freeness, they set a new benchmark for classical performance on bounded-degree problems. Future research may explore derandomization techniques and the extension of these bounds to general graphs without the triangle-free restriction.

Summary updated

BibTeX
@inproceedings{barak2015beating,
  author = {Boaz Barak and Ankur Moitra and Ryan O'Donnell and Prasad Raghavendra and Oded Regev and David Steurer and Luca Trevisan and Aravindan Vijayaraghavan and David Witmer and John Wright},
  title = {{Beating the Random Assignment on Constraint Satisfaction Problems of Bounded Degree}},
  booktitle = {APPROX-RANDOM},
  year = {2015},
  doi = {10.4230/lipics.approx-random.2015.110},
}
Figure