Unique Games on the Hypercube

2014/05/03 by Naman Agarwal, Agarwal, Naman, Guy Kindler +5
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.1405.1374

arxiv created 2014/05/03 · openalex publication_date 2014/05/03 · arxiv updated 2014/05/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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(ℤ₂). We conjecture that adding triangle inequalities to the SDP provides a polynomial time algorithm to solve Unique Games on the hypercube.

Citations

• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Related

• Playing Unique Games on Certified Small-Set Expanders
• Lower Bound for the Unique Games Problem
• Making the long code shorter, with applications to the Unique Games Conjecture
• Reduction From Non-Unique Games To Boolean Unique Games
• On the Unique Games Conjecture (Invited Survey)