Computing the Partition Function of a Polynomial on the Boolean Cube

Alexander Barvinok ()
Additional contact information
Alexander Barvinok: University of Michigan, Department of Mathematics

A chapter in A Journey Through Discrete Mathematics, 2017, pp 135-164 from Springer

Abstract: Abstract 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.

Keywords: 90C09; 68C25; 68W25; 68R05 (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-319-44479-6_7

Ordering information: This item can be ordered from
http://www.springer.com/9783319444796

DOI: 10.1007/978-3-319-44479-6_7

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().