We give a deterministic algorithm forapproximately counting satisfying assignments of a degree-d polynomial threshold function(PTF).Given a degree-d input polynomial p(x1xn) over Rnand a parameter 0">0, our algorithm approximatesPx−11n[p(x)0]to within an additive in time Od(1)poly(nd).(Since it is NP-hard to determine whether the above probabilityis nonzero, any sort of efficient multiplicative approximation isalmost certainly impossible even for randomized algorithms.)Note that the running time of our algorithm (as a function of nd,the number of coefficients of a degree-d PTF)is a \emph{fixed} polynomial. The fastest previous algorithm forthis problem (due to Kane), based on constructions ofunconditional pseudorandom generators for degree-d PTFs, runs in timenOdc(1)−c for all 0">c0.

The key novel contributions of this work are:

A new multivariate central limit theorem, proved using toolsfrom Malliavin calculus and Stein's Method. This new CLT shows that anycollection of Gaussian polynomials with small eigenvalues must have ajoint distribution which is very close to a multidimensional Gaussiandistribution.

A new decomposition of low-degree multilinear polynomials over Gaussianinputs. Roughly speaking we show that (up to some small error)any such polynomial can be decomposedinto a bounded number of multilinear polynomials all of which haveextremely small eigenvalues.

We use these new ingredients to give a deterministic algorithmfor a Gaussian-space version of the approximate counting problem,and then employ standard techniques for working withlow-degree PTFs (invariance principles and regularity lemmas)to reduce the original approximate counting problem over the Boolean hypercube to the Gaussianversion.

As an application of our result, we give the first deterministic fixed-parameter tractablealgorithm for the following moment approximation problem: given a degree-d polynomial p(x1xn) over −11n , a positive integerk and an error parameter , output a (1)-multiplicativelyaccurate estimate to Ex−11n[p(x)k] Our algorithmruns in time Odk(1)poly(nd)