  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(x_1,\dots,x_n)$ over $R^n$ and a parameter
$\epsilon> 0$, our algorithm approximates $\Pr_{x \sim \{-1,1\}^n}[p(x) \geq
0]$ to within an additive $\pm \epsilon$ in time $O_{d,\epsilon}(1)\cdot
\mathop{poly}(n^d)$. (Any sort of efficient multiplicative approximation is
impossible even for randomized algorithms assuming $NP\not=RP$.) Note that the
running time of our algorithm (as a function of $n^d$, the number of
coefficients of a degree-$d$ PTF) is a \emph{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^{O_{d,c}(1) \cdot \epsilon^{-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.
