Computing the Partition Function of a Polynomial on the Boolean Cube

For a polynomial $$f:\{ -1,1\}^{n}\longrightarrow \mathbb{C}$$ , we define the partition function as the average of e λf(x) over all points x ∈ {−1, 1} n , where $$\lambda \in \mathbb{C}$$ is a parameter. We present a quasi-polynomial algorithm, which, given such f, λ and ε > 0 approximates the partition function within a relative error of ε in N O(lnn−lnε) time provided $$\vert \lambda \vert \leq (2L\sqrt{\deg f})^{-1}$$ , 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 such that every variable enters not more than 4 monomials, approximates the maximum of f on { − 1, 1} n within a factor of $$O\left (\delta ^{-1}\sqrt{\deg f}\right )$$ , provided the maximum is Nδ for some 0 4, we are able to establish a similar result when δ ≥ (k − 1)∕k.