Paper Info
Title
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions.
Abstract
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 deterministic algorithm which, given as input explicit descriptions of g, q(1),..., q(k) and an accuracy parameter epsilon > 0, approximates Pr-x similar to{-1,Pr-1}n [g(sign(q(1)(x)),..., sign(q(k)(x))) = 1] to within an additive +/-epsilon. For any constant epsilon > 0 and k = 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small epsilon = o(n)(1) and not-too-large k = omega(n)(1)). This is the first fixed polynomialtime algorithm that can deterministically approximately count satisfying assignments of a natural class of depth-3 Boolean circuits. Our algorithm extends a recent result [1] 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. Note that even in the k = 1 case it is NP-hard to determine whether Pr-x similar to{-1,Pr-1}n[sign(q(x)) = 1] is nonzero, so any sort of multiplicative approximation is almost certainly impossible even for efficient randomized algorithms. Our algorithm and analysis requires several novel technical ingredients that go significantly beyond the tools required to handle the k = 1 case in [1]. 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, i.e., an algorithm for estimating Pr-x similar to N(0,Pr-1)n [g(sign(q(1)(x)),..., sign(q(k)(x))) = 1]. 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 [2], [3] (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al [4] (which applies to a k-tuples of linear threshold functions, i.e., the case d = 1). Our new regularity lemma lets us extend our deterministic approximate counting results from the Gaussian to the Boolean domain.
Year
DOI
Venue
2013
10.1109/CCC.2014.31
IEEE Conference on Computational Complexity
Keywords
DocType
Volume
Approximate counting,derandomization,polynomial threshold function
Journal
abs/1311.7115
ISSN
Citations 
PageRank 
1093-0159
2
0.36
References 
Authors
0
3
Name
Order
Citations
PageRank
Anindya De123924.77
Ilias Diakonikolas277664.21
Rocco A. Servedio31656133.28