Fetching the paper…
Reading the bibliography…
In this paper we show a new way of constructing deterministic polynomial-time approximation algorithms for computing complex-valued evaluations of a large class of graph polynomials on bounded degree graphs.
T. Lee and T. Yang, Statistical theory of equations of state and phase transitions. I. Theory of condensation, Physical Review
1952
Earlier work this paper cites.
P. de la Harpe, and V.F.R. Jones, Graph invariants related to statistical mechanical models: examples and problems, Journal of Combinatorial Theory
1993
Earlier work this paper cites.
M. Jerrum and A. Sinclair, Polynomial-time approximation algorithms for the Ising model, SIAM Journal on computing
1993
Earlier work this paper cites.
M. Jerrum, A very simple algorithm for estimating the number of k k -colorings of a low-degree graph, Random Structures and Algorithms
1995
Earlier work this paper cites.
J.B. Shearer, On a problem of Spencer, Combinatorica
1998
Earlier work this paper cites.
R. Bubley, M. Dyer, C. Greenhill and M. Jerrum: On approximately counting colorings of small degree graphs, SIAM Journal on Computing
1999
Earlier work this paper cites.
M. Dyer and C. Greenhill, On Markov chains for independent sets, Journal of Algorithms
2000
Earlier work this paper cites.
M. Dyer and C. Greenhill, The complexity of counting graph homomorphisms, Random Structures and Algorithms
2000
Earlier work this paper cites.
E. Vigoda, Improved bounds for sampling colorings, Journal of Mathematical Physics
2000
Earlier work this paper cites.
A. Sokal, A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models, Markov Processes And Related Fields
2001
Earlier work this paper cites.
B. Jackson, Zeros of chromatic and flow polynomials of graphs, Journal of Geometry 76
2003
Earlier work this paper cites.
A. Bulatov and M. Grohe, The complexity of partition functions, Theoretical Computer Science
2005
Earlier work this paper cites.
A.D. Scott and A.D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, Journal of Statistical Physics
2005
Earlier work this paper cites.
D. Weitz, Counting independent sets up to the tree threshold, in Proceedings of the thirty-eighth annual ACM symposium on Theory of computing
2006
Earlier work this paper cites.
M. Bayati, D. Gamarnik, D. Katz, C. Nair and P. Tetali, Simple deterministic approximation algorithms for counting matchings. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
2007
Earlier work this paper cites.
M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a clawfree graph, Journal of Combinatorial Theory, Series B
2007
Earlier work this paper cites.
B. Szegedy, Edge-coloring models and reflection positivity, Journal of the American Mathematical Society
2007
Earlier work this paper cites.
J. Cai, S. Huang and P. Lu, From Holant to #CSP and Back: Dichotomy for Holant c
2010
Cited alongside, same era.
B. Szegedy, Edge coloring models as singular vertex-coloring models, in: Fete of Combinatorics and Computer Science
2010
Cited alongside, same era.
J. Cai, P. Lu and M. Xia, Computational complexity of Holant problems, SIAM Journal on Computing
2011
Cited alongside, same era.
D. Gamarnik and D. Katz, Correlation decay and deterministic FPTAS for counting list-colorings of a graph, Journal of Discrete Algorithms
2012
Cited alongside, same era.
L.A. Goldberg and M. Jerrum, Approximating the partition function of the ferromagnetic Potts model, Journal of the ACM
2012
Cited alongside, same era.
2014
Later among the works it cites.
C. Lin, J. Liu and P. Lu, A simple FPTAS for counting edge covers, in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms
2014
Later among the works it cites.
A. Sinclair, P. Srivastava and M. Thurley, Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs, Journal of Statistical Physics
2014
Later among the works it cites.
A. Barvinok, Computing the partition function for cliques in a graph, Theory of Computing
2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
L.A. Goldberg, and M. Jerrum, The complexity of computing the sign of the Tutte polynomial (and consequent #P-hardness of approximation) In Automata, Languages, and Programming
2012
Cited alongside, same era.
A. Sly and N. Sun, The computational hardness of counting in two-spin models on d-regular graphs, in Proceedings of the 53rd Annual Symposium on Foundations of Computer Science
2012
Cited alongside, same era.
C. Borgs, J. Chayes, J. Kahn and L. Lovász, Left and right convergence of graphs with bounded degree, Random Structures and Algorithms
2013
Cited alongside, same era.
J. Cai, X. Chen and P. Lu, Graph homomorphisms with complex values: A dichotomy theorem, SIAM Journal on Computing
2013
Cited alongside, same era.
J. Cai, H. Guo and T. Williams, A complete dichotomy rises from the capture of vanishing signatures, In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing
2013
Cited alongside, same era.
B. Jackson, A. Procacci and A.D. Sokal, Complex zero-free regions at large | q | |q| for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights, Journal of Combinatorial Theory, Series B
2013
Cited alongside, same era.
P. Lu and Y. Yin, Improved FPTAS for multi-spin systems, in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
2013
Cited alongside, same era.
2015
Later among the works it cites.
A. Barvinok, Personal communication (2016)
2016
Closest in time.
A. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms, Combinatorica
2016
Closest in time.
A. Barvinok and P. Soberón, Computing the partition function for graph homomorphisms with multiplicities, Journal of Combinatorial Theory, Series A
2016
Closest in time.
P. Csikvári and P. E. Frenkel, Benjamini–Schramm continuity of root moments of graph polynomials, European Journal of Combinatorics
2016
Closest in time.
2016
Closest in time.
2016
Closest in time.
A. Barvinok, Approximating permanents and hafnians, Discrete Analysis
2017
Closest in time.
A. Barvinok, Combinatorics and Complexity of Partition Functions
2017
Closest in time.
2017
Closest in time.
2017
Closest in time.
G. Regts, Zero-free regions of partition functions with applications to algorithms and graph limits, Combinatorica
2017
Closest in time.