Computing the partition function of a polynomial on the Boolean cube

2015/03/25 by Barvinok, Alexander
#68C25 #68R05 #68W25 #90C09 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.1503.07463

Abstract

For a polynomial f: -1, 1ⁿ --> C, we define the partition function as the average of e^{lambda f(x)} over all points x in -1, 1ⁿ, 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 sqrtdeg 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ⁿ within a factor of O(sqrtdeg 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.

Related

• A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
• On the weight and density bounds of polynomial threshold functions
• Polynomial Threshold Functions: Structure, Approximation and Pseudorandomness
• A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
• Sylvester-Cayley vector partitions algorithm and the Gaussian polynomials