Efficient deterministic approximate counting for low-degree polynomial threshold functions

We give a deterministic algorithm for approximately counting satisfying assignments of a degree-d polynomial threshold function (PTF). Given a degree-d input polynomial p(x1,dots,xn) over Rn and a parameter ε> 0, our algorithm approximates Pr_x ~ -1,1n[p(x) ≥ 0] to within an additive ± ε in time Od,ε(1)· mathoppoly(nd). (Any sort of efficient multiplicative approximation is impossible even for randomized algorithms assuming NPnot=RP.) Note that the running time of our algorithm (as a function of nd, the number of coefficients of a degree-d PTF) is a fixed polynomial. The fastest previous algorithm for this problem (due to Kane), based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time n^Od,c(1) · ε-c for all c > 0. The key novel contributions of this work are: A new multivariate central limit theorem, proved using tools from Malliavin calculus and Stein's Method. This new CLT shows that any collection of Gaussian polynomials with small eigenvalues must have a joint distribution which is very close to a multidimensional Gaussian distribution. A new decomposition of low-degree multilinear polynomials over Gaussian inputs. Roughly speaking we show that (up to some small error) any such polynomial can be decomposed into a bounded number of multilinear polynomials all of which have extremely small eigenvalues. We use these new ingredients to give a deterministic algorithm for a Gaussian-space version of the approximate counting problem, and then employ standard techniques for working with low-degree PTFs (invariance principles and regularity lemmas) to reduce the original approximate counting problem over the Boolean hypercube to the Gaussian version.