Implementations and the independent set polynomial below the Shearer threshold

On a problem of Spencer

J. B. Shearer · 1985

Earlier work this paper cites.

The repulsive lattice gas, the independent-set polynomial, and the Lovász Local Lemma

Alexander D. Scott and Alan D. Sokal · 2005

Earlier work this paper cites.

Counting independent sets up to the tree threshold

Dror Weitz · 2006

Earlier work this paper cites.

A constructive proof of the general Lovász Local lemma

Robin A. Moser and Gábor Tardos · 2010

Earlier work this paper cites.

Counting in two-spin models on d-regular graphs

Allan Sly and Nike Sun · 2014

Earlier work this paper cites.

Approximating the hard core partition function with negative activities

Piyush Srivastava · 2015

Cited alongside, same era.

The complexity of approximately counting in 2-spin systems on k-uniform bounded-degree hypergraphs

Andreas Galanis and Leslie Ann Goldberg · 2016

Cited alongside, same era.

Inapproximability of the partition function for the antiferromagnetic Ising and hard-core models

Andreas Galanis, Daniel Štefankovič, and Eric Vigoda · 2016

Cited alongside, same era.

Computing the independence polynomial in shearer’s region for the LLL

Original

Nicholas J. A. Harvey, Piyush Srivastava, and Jan Vondrák · 2016

Cited alongside, same era.

Inapproximability of the independent set polynomial below the Shearer threshold

Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic · 2017

Cited alongside, same era.

Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials

Viresh Patel and Guus Regts · 2017

Closest in time.

Inapproximability of the independent set polynomial in the complex plane

Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, and Daniel Stefankovic · 2018

Closest in time.

Computing the independence polynomial: from the tree threshold down to the roots

Nicholas J. A. Harvey, Piyush Srivastava, and Jan Vondrák · 2018

Closest in time.

Uniform sampling through the lovász local lemma

Heng Guo, Mark Jerrum, and Jingcheng Liu · 2019

Closest in time.

Approximate counting, the Lovász Local Lemma, and inference in graphical models

Ankur Moitra · 2019

Closest in time.