Computing the partition function of a polynomial on the Boolean cube
Alexander I. Barvinok · arXiv (Cornell University) · 2015
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| 4, we are able to establish a similar result when delta > (k-1)/k.