A. De and R. Servedio.

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 $\eps > 0$, our algorithm approximates
$
\Pr_{x \sim \{-1,1\}^n}[p(x) \geq 0]
$
to within an additive $\pm \eps$ in time $O_{d,\eps}(1)\cdot \poly(n^d)$.
(Since it is NP-hard to determine whether the above probability
is nonzero, any sort of efficient multiplicative approximation is
almost certainly impossible even for randomized algorithms.)
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 \cite{Kane12subpoly}, based on constructions of
unconditional pseudorandom generators for degree-$d$ PTFs, runs in time
$n^{O_{d,c}(1) \cdot \eps^{-c}}$ for all $c > 0$.

The key novel contributions of this work are

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.

pdf of conference version