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

MaRDI QIDQ6246814zbMATH OpenFDO

Authors Anindya De, Ilias Diakonikolas, Rocco A. Servedio

Publication date 27 November 2013

Abstract: Let $g:{-1,1}^{k}o-1,1$ be any Boolean function and $q_1,dots,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,dots,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 $pmeps$. For any constant $eps>0$ and $kgeq1$ 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.

This page was built for publication: Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6246814)