A new point of NP-hardness for unique games

2012/05/19 by Ryan O’Donnell, John C. Wright · 34 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Alphabet #Approximation algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Exponential function #Formal Methods in Verification #Geometry #Hardness of approximation #Mathematical analysis #Mathematics #Philosophy #Point (geometry)

paper · doi:10.1145/2213977.2214005

openalex publication_date 2012/05/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We show that distinguishing 1/2-satisfiable Unique-Games instances from (3/8 + ε)-satisfiable instances is NP-hard (for all ε > 0). A consequence is that we match or improve 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 alphabet size larger than 2. Our NP-hardness reductions are quasilinear-size and thus show nearly full exponential time is required, assuming the ETH.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Clique is hard to approximate within n1−ε
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On the power of unique 2-prover 1-round games
• On the hardness of approximating vertex cover
• Clique is hard to approximate within n/sup 1-ε/
• Relations between average case complexity and approximation complexity
• Subexponential Algorithms for Unique Games and Related Problems

Cited by

• Unique games conjecture [wikipedia]

Related

• Strengthened Hardness for Approximating Minimum Unique Game and Small Set Expansion
• Approximation Algorithms and Hardness for Strong Unique Games
• How to Play Unique Games against a Semi-Random Adversary
• NP-Hardness of a 2D, a 2.5D, and a 3D Puzzle Game
• On the Emergence of Ergodic Dynamics in Unique Games