Fetching the paper…
Reading the bibliography…
We prove that the logarithm of the permanent of an nxn real matrix A and the logarithm of the hafnian of a 2nx2n real symmetric matrix A can be approximated within an additive error 1 > epsilon > 0 by a polynomial p in the entries of A of degree O(ln n - ln epsilon) provided the entries a_ij of A satisfy delta < a_ij < 1 for an arbitrarily small delta > 0, fixed in advance.
Geometry of Polynomials. Second edition
Morris Marden · 1966
Earlier work this paper cites.
Theory of monomer-dimer systems
Ole J. Heilmann and Elliott H. Lieb · 1972
Earlier work this paper cites.
Permanents
Henryk Minc · 1978
Earlier work this paper cites.
The complexity of computing the permanent
Leslie G. Valiant · 1979
Earlier work this paper cites.
Two algorithmic results for the traveling salesman problem
Alexander Barvinok · 1996
Earlier work this paper cites.
Polynomial time algorithms to approximate permanents and mixed discriminants within a simply exponential factor
Alexander Barvinok · 1999
Earlier work this paper cites.
Fast convergence of the Glauber dynamics for sampling independent sets
Michael Luby and Eric Vigoda · 1999
Earlier work this paper cites.
Approximating permanents of complex matrices
Martin Fürer · 2000
Earlier work this paper cites.
A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
Nathan Linial, Alex Samorodnitsky, and Avi Wigderson · 2000
Earlier work this paper cites.
The zeros of the partial sums of the exponential series
Peter Walker · 2003
Earlier work this paper cites.
Concentration of permanent estimators for certain large matrices
Shmuel Friedland, Brian Rider and Ofer Zeitouni · 2004
Earlier work this paper cites.
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Mark Jerrum, Alistair Sinclair and Eric Vigoda · 2004
Earlier work this paper cites.
On the complexity of mixed discriminants and related problems
Leonid Gurvits · 2005
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
Cited alongside, same era.
Counting independent sets up to the tree threshold
Dror Weitz · 2006
Cited alongside, same era.
Simple deterministic approximation algorithms for counting matchings
Mohsen Bayati, David Gamarnik, Dimitriy Katz, Chandra Nair and Prasad Tetali · 2007
Cited alongside, same era.
The roots of the independence polynomial of a clawfree graph
Maria Chudnovsky and Paul Seymour · 2007
Cited alongside, same era.
The Lee-Yang and Pólya-Schur programs. II. Theory of stable polynomials and applications
Julius Borcea and Petter Brändén · 2009
Cited alongside, same era.
Matching Theory
László Lovász and Michael D. Plummer · 2009
Cited alongside, same era.
Computing the partition function for cliques in a graph
Alexander Barvinok · 2015
Later among the works it cites.
Personal communication, 2015
Boris Bukh · 2015
Later among the works it cites.
Interlacing families II: Mixed characteristic polynomials and the Kadison-Singer problem
Adam W. Marcus, Daniel A. Spielman and Nikhil Srivastava · 2015
Later among the works it cites.
Zero-free regions of partition functions with applications to algorithms and graph limits
Guus Regts · 2015
Later among the works it cites.
Computing the permanent of (some) complex matrices
Alexander Barvinok · 2016
Closest in time.
Computing the partition function for graph homomorphisms with multiplicities
Alexander Barvinok and Pablo Soberón · 2016
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
A deterministic approximation algorithm for computing the permanent of a 0, 1 matrix
David Gamarnik and Dimitriy Katz · 2010
Cited alongside, same era.
Computing the partition function for perfect matchings in a hypergraph
Alexander Barvinok and Alex Samorodnitsky · 2011
Cited alongside, same era.
The computational complexity of linear optics
Scott Aaronson and Alex Arkhipov · 2013
Cited alongside, same era.
Bounds on the permanent and some applications
Leonid Gurvits and Alex Samorodnitsky · 2014
Cited alongside, same era.
Gaussian noise sensitivity and BosonSampling
Gil Kalai and Guy Kindler · 2014
Cited alongside, same era.
An upper bound on the number of high-dimensional permutations
Nathan Linial and Zur Luria · 2014
Cited alongside, same era.
An efficient tree decomposition method for permanents and mixed discriminants
Diego Cifuentes and Pablo A. Parrilo · 2016
Closest in time.
Benjamini-Schramm continuity of root moments of graph polynomials
Péter Csikvári and Péter E. Frenkel · 2016
Closest in time.
Computing the independence polynomial in Shearer’s region for the LLL
Nicholas J. A. Harvey, Piyush Srivastava and Jan Vondrák · 2016
Closest in time.
The quantum computer puzzle (expanded version)
Gil Kalai · 2016
Closest in time.
The complex roots and approximation of permanents
Max Kontorovich and Han Wu · 2016
Closest in time.
Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials
Viresh Patel and Guus Regts · 2016
Closest in time.
Random Gaussian matrices and Hafnian estimators
Mark Rudelson, Alex Samorodnitsky and Ofer Zeitouni · 2016
Closest in time.