Fetching the paper…
Reading the bibliography…
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.
A deterministic algorithm for counting colorings with 2 Δ 2\Delta colors
J. Liu, A. Sinclair, and P. Srivastava · 1906
Earlier work this paper cites.
C. Borgs, J. Chayes, T. Helmuth, W. Perkins, and P. Tetali · 1909
Earlier work this paper cites.
.879-approximation algorithms for MAX CUT and MAX 2SAT
M. X. Goemans and D. P. Williamson · 1994
Earlier work this paper cites.
On the Lambert W W function
R. M. Corless, G. H. Gonnet, D. E. G. Hare, D. J. Jeffrey, and D. E. Knuth · 1996
Earlier work this paper cites.
The random-cluster model on a homogeneous tree
O. Häggström · 1996
Earlier work this paper cites.
How good is the Goemans–Williamson MAX CUT algorithm?
H. J. Karloff · 1996
Earlier work this paper cites.
On the optimality of the random hyperplane rounding technique for MAX CUT
U. Feige and G. Schechtman · 2002
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
S. Khot · 2002
Earlier work this paper cites.
Vertex Cover Might be Hard to Approximate to within 2 − ε 2-\varepsilon
S. Khot and O. Regev · 2003
Earlier work this paper cites.
Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs?
S. Khot, G. Kindler, E. Mossel, and R. O’Donnell · 2004
Earlier work this paper cites.
On the hardness of approximating multicut and sparsest-cut
S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar · 2005
Earlier work this paper cites.
The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into ℓ 1 \ell_{1}
S. Khot and N. K. Vishnoi · 2005
Cited alongside, same era.
Unique games on expanding constraint graphs are easy: extended abstract
S. Arora, S. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. K. Vishnoi · 2008
Cited alongside, same era.
Optimal algorithms and inapproximability results for every CSP?
P. Raghavendra · 2008
Cited alongside, same era.
Subexponential algorithms for unique games and related problems
S. Arora, B. Barak, and D. Steurer · 2010
Cited alongside, same era.
Improved algorithms for unique games via divide and conquer
S. Arora, R. Impagliazzo, W. Matthews, and D. Steurer · 2010
Cited alongside, same era.
Spectral algorithms for unique games
A. Kolla · 2010
Ferromagnetic Potts model: Refined #BIS-hardness and related results
A. Galanis, D. Stefankovic, E. Vigoda, and L. Yang · 2016
Later among the works it cites.
Deterministic Polynomial-Time Approximation Algorithms for Partition Functions and Graph Polynomials
V. Patel and G. Regts · 2017
Later among the works it cites.
Deterministic search for CNF satisfying assignments in almost polynomial time
R. A. Servedio and L. Tan · 2017
Later among the works it cites.
Approximating real-rooted and stable polynomials, with combinatorial applications
A. Barvinok · 2018
Later among the works it cites.
On zero-free regions for the anti-ferromagnetic Potts model on bounded-degree graphs
F. Bencs, E. Davies, V. Patel, and G. Regts · 2018
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
How to play unique games on expanders
K. Makarychev and Y. Makarychev · 2010
Cited alongside, same era.
Graph expansion and the unique games conjecture
P. Raghavendra and D. Steurer · 2010
Cited alongside, same era.
Combinatorics and complexity of partition functions
A. Barvinok · 2016
Cited alongside, same era.
Mixing of the Glauber dynamics for the ferromagnetic Potts model
M. Bordewich, C. S. Greenhill, and V. Patel · 2016
Cited alongside, same era.
On non-optimally expanding sets in Grassmann graphs
I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra · 2018
Later among the works it cites.
Towards a proof of the 2-to-1 games conjecture?
I. Dinur, S. Khot, G. Kindler, D. Minzer, and M. Safra · 2018
Later among the works it cites.
Location of zeros for the partition function of the Ising model on bounded degree graphs
H. Peters and G. Regts · 2018
Later among the works it cites.
Algorithmic Pirogov-Sinai theory
T. Helmuth, W. Perkins, and G. Regts · 2019
Closest in time.
Computing the number of induced copies of a fixed graph in a bounded degree graph
V. Patel and G. Regts · 2019
Closest in time.