Locally Expanding Hypergraphs and the Unique Games Conjecture
Eric Purdy · 2008
We examine the hardness of approximating constraint satisfaction problems with k-variable constraints, known as k-CSP’s. We are specifically interested in k-CSP’s whose constraints are unique, which means that for any assignment to any k − 1 of the variables, there is a unique assignment to the last variable satisfying the constraint. One fundamental example of these CSP’s is Ek-Lin-p, the problem of satisfying as many equations as possible from an over-determined system of linear equations modulo a prime p, where each equation contains exactly k variables. The central question in much of the recent work on inapproximability has been the Unique Games Conjecture, which posits a very strong hardness of approximation for 2-CSP’s with unique constraints, such as E2-Lin-p. Many strong inapproximability results have been proven assuming that it is true, including a recent result of Raghavendra (“Optimal algorithms and inapproximability results for every CSP? ” in STOC. ACM, 2008.) giving an approximation algorithm for every CSP, whose performance is essentially optimal if the Unique Games Conjecture is true. To date, however, not much progress has been made on resolving the conjecture. In this paper, we give a reduction from unique 3-CSP’s to unique 2-CSP’s which is sometimes approximation-preserving, depending on the combinatorial structure of the underlying hypergraph of the 3-CSP. The underlying hypergraph of a 3-CSP is the hypergraph in which each vertex represents a variable, and every hyperedge represents a constraint. Every constraint c yields a hyperedge between the three variables involved in c. The reduction only works when the underlying hypergraph of the 3-CSP satisfies a (hypergraph) expansion property, which we call local expansion. We prove that the Unique Games Conjecture is equivalent to a hardness result for unique 3-CSP’s whose underlying hypergraphs are local expanders. We give a precise formulation of the desired hardness result as a conjecture, which we call the Expanding Unique 3-CSP’s Conjecture. We also give a restricted, but still equivalent, conjecture that E3-Lin-p is