A new point of NP-hardness for Unique Games
May 2, 2012
ABSTRACT:
Perhaps the single most important open problem in the field of hardness of approximation is the Unique Games Conjecture. This conjecture states that given a nearly satisfiable set of two-variable linear equations modulo some integer q (aka the "Unique Games" problem), it is NP-hard to find an assignment to the variables that satisfies even a small fraction of the equations. Using this conjecture as a starting point, we now have a (basically) perfect understanding of the (in-)approximability of a large number of problems. Unfortunately, evidence for this conjecture is thin: for example, the best NP-hardness known for two-variable linear equations is for linear equations just mod 2, even though all other signs point towards linear equations mod q substantially growing in hardness as q increases.
In this talk, I'll show that distinguishing 1/2-satisfiable Unique Games instances from (3/8 + eps)-satisfiable instances is NP-hard (for all eps > 0). A consequence is that this matches or improves the best known c vs. s NP-hardness result for Unique Games for all values of c (except for c very close to 0). For these c, ours is the first hardness result showing that it helps to take the equations modulo a q greater than 2. Our NP-hardness reductions are quasilinear-size and thus show nearly full exponential time is required, assuming the Exponential Time Hypothesis.
Based on joint work with Ryan O'Donnell.
Perhaps the single most important open problem in the field of hardness of approximation is the Unique Games Conjecture. This conjecture states that given a nearly satisfiable set of two-variable linear equations modulo some integer q (aka the "Unique Games" problem), it is NP-hard to find an assignment to the variables that satisfies even a small fraction of the equations. Using this conjecture as a starting point, we now have a (basically) perfect understanding of the (in-)approximability of a large number of problems. Unfortunately, evidence for this conjecture is thin: for example, the best NP-hardness known for two-variable linear equations is for linear equations just mod 2, even though all other signs point towards linear equations mod q substantially growing in hardness as q increases.
In this talk, I'll show that distinguishing 1/2-satisfiable Unique Games instances from (3/8 + eps)-satisfiable instances is NP-hard (for all eps > 0). A consequence is that this matches or improves the best known c vs. s NP-hardness result for Unique Games for all values of c (except for c very close to 0). For these c, ours is the first hardness result showing that it helps to take the equations modulo a q greater than 2. Our NP-hardness reductions are quasilinear-size and thus show nearly full exponential time is required, assuming the Exponential Time Hypothesis.
Based on joint work with Ryan O'Donnell.