Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

A Journey Through Discrete MathematicsComputing the Partition Function of a Polynomial on the Boolean Cube

A Journey Through Discrete Mathematics: Computing the Partition Function of a Polynomial on the... [For a polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$f:\{ -1,1\}^{n}\longrightarrow \mathbb{C}$$ \end{document}, we define the partition function as the average of eλf(x) over all points x ∈ {−1, 1}n, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\lambda \in \mathbb{C}$$ \end{document} 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 NO(lnn−lnε) time provided \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\vert \lambda \vert \leq (2L\sqrt{\deg f})^{-1}$$ \end{document}, 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O\left (\delta ^{-1}\sqrt{\deg f}\right )$$ \end{document}, provided the maximum is Nδ for some 0 < δ ≤ 1. If every variable enters not more than k monomials for some fixed k > 4, we are able to establish a similar result when δ ≥ (k − 1)∕k.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

A Journey Through Discrete MathematicsComputing the Partition Function of a Polynomial on the Boolean Cube

Editors: Loebl, Martin; Nešetřil, Jaroslav; Thomas, Robin
Barvinok, Alexander
Springer Journals — May 9, 2017
Download PDF
29 pages

Loading next page...
 
/lp/springer-journals/a-journey-through-discrete-mathematics-computing-the-partition-02TEMYo5j9
Publisher
Springer International Publishing
Copyright
© Springer International publishing AG 2017
ISBN
978-3-319-44478-9
Pages
135 –164
DOI
10.1007/978-3-319-44479-6_7
Publisher site
See Chapter on Publisher Site

Abstract

[For a polynomial \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$f:\{ -1,1\}^{n}\longrightarrow \mathbb{C}$$ \end{document}, we define the partition function as the average of eλf(x) over all points x ∈ {−1, 1}n, where \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\lambda \in \mathbb{C}$$ \end{document} 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 NO(lnn−lnε) time provided \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$\vert \lambda \vert \leq (2L\sqrt{\deg f})^{-1}$$ \end{document}, 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 \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document} $$O\left (\delta ^{-1}\sqrt{\deg f}\right )$$ \end{document}, provided the maximum is Nδ for some 0 < δ ≤ 1. If every variable enters not more than k monomials for some fixed k > 4, we are able to establish a similar result when δ ≥ (k − 1)∕k.]

Published: May 9, 2017

Keywords: 90C09; 68C25; 68W25; 68R05

There are no references for this article.