Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions.

Let g:{−1,1} k →{−1,1} be any Boolean function and q 1 ,…,q k be any degree-2 polynomials over {−1,1} n . We give a \emph{deterministic} algorithm which, given as input explicit descriptions of g,q 1 ,…,q k and an accuracy parameter $\eps>0$, approximates \Pr_{x \sim \{-1,1\}^n}[g(\sign(q_1(x)),\dots,\sign(q_k(x)))=1] to within an additive $\pm \eps$. For any constant $\eps > 0$ and k≥1 the running time of our algorithm is a fixed polynomial in n . This is the first fixed polynomial-time algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result \cite{DDS13:deg2count} which gave a deterministic approximate counting algorithm for a single degree-2 polynomial threshold function $\sign(q(x)),$ corresponding to the k=1 case of our result.
Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k=1 case in \cite{DDS13:deg2count}. One of these is a new multidimensional central limit theorem for degree-2 polynomials in Gaussian random variables which builds on recent Malliavin-calculus-based results from probability theory. We use this CLT as the basis of a new decomposition technique for k -tuples of degree-2 Gaussian polynomials and thus obtain an efficient deterministic approximate counting algorithm for the Gaussian distribution. Finally, a third new ingredient is a "regularity lemma" for \emph{k -tuples} of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of \cite{DSTW:10,HKM:09} and the regularity lemma of Gopalan et al \cite{GOWZ10}. Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.