Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-173 | 28th November 2013 22:23

Efficient deterministic approximate counting for low degree polynomial threshold functions


Authors: Anindya De, Rocco Servedio
Publication: 3rd December 2013 22:24
Downloads: 1918


We give a deterministic algorithm for
approximately counting satisfying assignments of a degree-$d$ polynomial threshold function
Given a degree-$d$ input polynomial $p(x_1,\dots,x_n)$ over $\mathbb{R}^n$
and a parameter $\epsilon > 0$, our algorithm approximates
\mathbf{P}_{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)$.
(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 (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

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

As an application of our result, we give the first deterministic fixed-parameter tractable
algorithm for the following moment approximation problem: given a degree-$d$ polynomial $p(x_1,\dots,x_n)$ over $\{-1,1\}^n$, a positive integer
$k$ and an error parameter $\epsilon$, output a $(1\pm \epsilon)$-multiplicatively
accurate estimate to $\mathbf{E}_{x \sim \{-1,1\}^n}[|p(x)|^k].$ Our algorithm
runs in time $O_{d,\epsilon,k}(1) \cdot \mathop{poly}(n^d).$

ISSN 1433-8092 | Imprint