TY - GEN
T1 - Deterministic approximate counting for juntas of degree-2 polynomial threshold functions
AU - De, Anindya
AU - Diakonikolas, Ilias
AU - Servedio, Rocco A.
PY - 2014
Y1 - 2014
N2 - Let g: {-1, 1}k to {-1, 1} be any Boolean function and q-1, ⋯, 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 ε>0, approximates [epqution presented] to within an additive pm eps. For any constant eps > 0 and k geq 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ε = on(1) and not-too-large k = ωn(1)). 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 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. Note that even in the k=1 case it is NP-hard to determine whether Prx ∼ {-1, 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 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, i.e., an algorithm for estimating [ Prx ∼ N(0, 1)n}[g(sign(q1(x)), dots, sign(qk(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 DSTW:10, HKM:09 (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al GOWZ10 (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.
AB - Let g: {-1, 1}k to {-1, 1} be any Boolean function and q-1, ⋯, 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 ε>0, approximates [epqution presented] to within an additive pm eps. For any constant eps > 0 and k geq 1 the running time of our algorithm is a fixed polynomial in n (in fact this is true even for some not-too-small ε = on(1) and not-too-large k = ωn(1)). 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 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. Note that even in the k=1 case it is NP-hard to determine whether Prx ∼ {-1, 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 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, i.e., an algorithm for estimating [ Prx ∼ N(0, 1)n}[g(sign(q1(x)), dots, sign(qk(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 DSTW:10, HKM:09 (which apply to a single degree-d polynomial threshold function) and the regularity lemma of Gopalan et al GOWZ10 (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.
KW - Approximate counting
KW - derandomization
KW - polynomial threshold function
UR - http://www.scopus.com/inward/record.url?scp=84906669764&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84906669764&partnerID=8YFLogxK
U2 - 10.1109/CCC.2014.31
DO - 10.1109/CCC.2014.31
M3 - Conference contribution
AN - SCOPUS:84906669764
SN - 9781479936267
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 229
EP - 240
BT - Proceedings - IEEE 29th Conference on Computational Complexity, CCC 2014
PB - IEEE Computer Society
T2 - 29th Annual IEEE Conference on Computational Complexity, CCC 2014
Y2 - 11 June 2014 through 13 June 2014
ER -