Efficient Deterministic Approximate Counting for Low-Degree Polynomial Threshold Functions.
A. De and R. Servedio.
46th Annual Symposium on Theory of Computing (STOC), 2014, pp. 832--841.


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

  • 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.

    pdf of conference version

    Link to full version on ArXiV

    Back to main papers page