2013/11/27 by De, Anindya, Diakonikolas, Ilias, Servedio, Rocco A. · 1 citation
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1311.7115
Let g: \-1,1\k → \-1,1\ be any Boolean function and q1,…,qk be any degree-2 polynomials over \-1,1\n. We give a deterministic algorithm which, given as input explicit descriptions of g,q1,…,qk and an accuracy parameter \eps>0, approximates Pr_x ∼ \-1,1\n[g(\sign(q1(x)),…,\sign(qk(x)))=1] to within an additive ± \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 \citeDDS13: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 \citeDDS13: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 k-tuples of degree-d polynomial threshold functions. This generalizes both the regularity lemmas of \citeDSTW:10,HKM:09 and the regularity lemma of Gopalan et al \citeGOWZ10. Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.