Computing the partition function of a polynomial on the Boolean cube
From MaRDI portal
Abstract: For a polynomial f: {-1, 1}^n --> C, we define the partition function as the average of e^{lambda f(x)} over all points x in {-1, 1}^n, where lambda in C is a parameter. We present a quasi-polynomial algorithm, which, given such f, lambda and epsilon >0 approximates the partition function within a relative error of epsilon in N^{O(ln n -ln epsilon)} time provided |lambda| < 1/(2 L sqrt{deg f}), where L=L(f) is a parameter bounding the Lipschitz constant of f from above and N is the number of monomials in f. As a corollary, we obtain a quasi-polynomial algorithm, which, given such an f with coefficients +1 and -1 and such that every variable enters not more than 4 monomials, approximates the maximum of f on {-1, 1}^n within a factor of O(sqrt{deg f}/delta), provided the maximum is N delta for some 0< delta <1. If every variable enters not more than k monomials for some fixed k > 4, we are able to establish a similar result when delta > (k-1)/k.
Recommendations
- More on zeros and approximation of the Ising partition function
- A Note on Deterministic Poly-Time Algorithms for Partition Functions Associated with Boolean Matrices with Prescribed Row and Column Sums
- Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems
- Boolean matrices with prescribed row/column sums and stable homogeneous polynomials: combinatorial and algorithmic applications
- Computing the partition function for graph homomorphisms with multiplicities
Cites work
- Beating the random assignment on constraint satisfaction problems of bounded degree
- Completely analytical interactions: Constructive description
- Computing the partition function for cliques in a graph
- Computing the partition function for graph homomorphisms with multiplicities
- Computing the permanent of (some) complex matrices
- Counting independent sets up to the tree threshold
- Counting without sampling: Asymptotics of the log-partition function for certain statistical physics models
- Grothendieck-type inequalities in combinatorial optimization
- Inclusion-exclusion: exact and approximate
- Linear degree extractors and the inapproximability of max clique and chromatic number
- On bounded occurrence constraint satisfaction
- On the advantage over a random assignment
- Pseudo-Boolean optimization
- Some optimal inapproximability results
- Statistical Theory of Equations of State and Phase Transitions. I. Theory of Condensation
- Statistical Theory of Equations of State and Phase Transitions. II. Lattice Gas and Ising Model
- Zero-free regions of partition functions with applications to algorithms and graph limits
Cited in
(8)- Evaluations of the circuit partition polynomial
- Partitioning via Non-linear Polynomial Functions: More Compact IBEs from Ideal Lattices and Bilinear Maps
- scientific article; zbMATH DE number 3863201 (Why is no real title available?)
- More on zeros and approximation of the Ising partition function
- Weighted counting of solutions to sparse systems of equations
- Counting independent sets in graphs with bounded bipartite pathwidth
- Correlation decay and the absence of zeros property of partition functions
- Spectral independence via stability and applications to Holant-type problems
This page was built for publication: Computing the partition function of a polynomial on the Boolean cube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4604373)
