Statistical physics approaches to Unique Games

Abstract

We show how two techniques from statistical physics can be adapted to solve a variant of the notorious Unique Games problem, potentially opening new avenues towards the Unique Games Conjecture. The variant, which we call Count Unique Games, is a promise problem in which the "yes" case guarantees a certain number of highly satisfiable assignments to the Unique Games instance. In the standard Unique Games problem, the "yes" case only guarantees at least one such assignment. We exhibit efficient algorithms for Count Unique Games based on approximating a suitable partition function for the Unique Games instance via (i) a zero-free region and polynomial interpolation, and (ii) the cluster expansion. We also show that a modest improvement to the parameters for which we give results would refute the Unique Games Conjecture.

arXiv comment26 pages

References in corpus (5)

• Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
• Location of zeros for the partition function of the Ising model on bounded degree graphs
• Correlation decay and partition function zeros: Algorithms and phase transitions
• On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
• Efficient sampling and counting algorithms for the Potts model on ${\mathbb{Z}}^d$ at all temperatures

Cited by in corpus (1)

• Efficient algorithms for the Potts model on small-set expanders