2013

Inapproximability for Antiferromagnetic Spin Systems in the Tree Non-Uniqueness Region

Galanis, Andreas, Stefankovic, Daniel, Vigoda, Eric

Understand

A remarkable connection has been established for antiferromagnetic 2-spin systems, including the Ising and hard-core models, showing that the computational complexity of approximating the partition function for graphs with maximum degree D undergoes a phase transition that coincides with the statistical physics uniqueness/non-uniqueness phase transition on the infinite D-regular tree.

Despite this clear picture for 2-spin systems, there is little known for multi-spin systems.
We present the first analog of the above inapproximability results for multi-spin systems.
The main difficulty in previous inapproximability results was analyzing the behavior of the model on random D-regular bipartite graphs, which served as the gadget in the reduction.

Built on

Schur multipliers
G. Bennett · 1977
Earlier work this paper cites.
Asymptotic methods in analysis
N. G. de Bruijn · 1981
Earlier work this paper cites.
Loss networks
F. P. Kelly · 1991
Earlier work this paper cites.
Almost all regular graphs are Hamiltonian
R. W. Robinson and N. C. Wormald · 1994
Earlier work this paper cites.
Random regular graphs: asymptotic distributions and contiguity
Svante Janson · 1995
Earlier work this paper cites.
Asymptotic choice number for triangle free graphs
A. Johansson · 1996
Earlier work this paper cites.
Hardness of approximating problems on cubic graphs
Paola Alimonti and Viggo Kann · 1997
Earlier work this paper cites.
The complexity of counting colourings and independent sets in sparse graphs and hypergraphs
Catherine Greenhill · 2000
Earlier work this paper cites.
Random graphs
Svante Janson, Tomasz Łuczak, and Andrzej Rucinski · 2000
Earlier work this paper cites.

Similar

Colouring graphs when the number of colours is nearly the maximum degree
Michael Molloy and Bruce A. Reed · 2001
Cited alongside, same era.
Random colorings of a Cayley tree
G. R. Brightwell and P. Winkler · 2002
Cited alongside, same era.
Uniqueness of uniform random colorings of regular trees
Johan Jonasson · 2002
Cited alongside, same era.
Graph colouring and the probabilistic method
Michael Molloy and Bruce Reed · 2002
Cited alongside, same era.
The computational complexity of two-state spin systems
Leslie Ann Goldberg, Mark Jerrum, and Mike Paterson · 2003
Cited alongside, same era.
Counting independent sets up to the tree threshold
Dror Weitz · 2006
Cited alongside, same era.
Linear and nonlinear programming
David G. Luenberger and Yinyu Ye · 2008
Cited alongside, same era.
On the hardness of sampling independent sets beyond the tree threshold
Elchanan Mossel, Dror Weitz, and Nicholas Wormald · 2009
Cited alongside, same era.
A constructive proof of the general Lovász local lemma
Robin A. Moser and Gábor Tardos · 2010
Cited alongside, same era.

Then

Computational transition at the uniqueness threshold
Allan Sly · 2010
Later among the works it cites.
Gibbs measures and phase transitions
Hans-Otto Georgii · 2011
Later among the works it cites.
Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models
Original
Andreas Galanis, Daniel Štefankovič, and Eric Vigoda · 2012
Later among the works it cites.
Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs
Alistair Sinclair, Piyush Srivastava, and Marc Thurley · 2012
Later among the works it cites.
The computational hardness of counting in two-spin models on d-regular graphs
Allan Sly and Nike Sun · 2012
Later among the works it cites.
Matrix analysis
Roger A. Horn and Charles R. Johnson · 2013
Closest in time.
Correlation decay up to uniqueness in spin systems
Liang Li, Pinyan Lu, and Yitong Yin · 2013
Closest in time.
Improved inapproximability results for counting independent sets in the hard-core model
Andreas Galanis, Qi Ge, Daniel Štefankovič, Eric Vigoda, and Linji Yang · 2014
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…