2013/11/28 by De, Anindya, Servedio, Rocco · 2 citations
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1311.7178
We give a deterministic algorithm for approximately counting satisfying assignments of a degree-d polynomial threshold function (PTF). Given a degree-d input polynomial p(x1,…,xn) over Rn and a parameter ε> 0, our algorithm approximates Pr_x ∼ \-1,1\n[p(x) ≥ 0] to within an additive ± ε in time Od,ε(1)⋅ \mathoppoly(nd). (Any sort of efficient multiplicative approximation is impossible even for randomized algorithms assuming NP\not=RP.) Note that the running time of our algorithm (as a function of nd, the number of coefficients of a degree-d PTF) is a fixed polynomial. The fastest previous algorithm for this problem (due to Kane), based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time n^Od,c(1) ⋅ ε-c for all c > 0. The key novel contributions of this work are: A new multivariate central limit theorem, proved using tools from Malliavin calculus and Stein's Method. This new CLT shows that any collection of Gaussian polynomials with small eigenvalues must have a joint distribution which is very close to a multidimensional Gaussian distribution. A new decomposition of low-degree multilinear polynomials over Gaussian inputs. Roughly speaking we show that (up to some small error) any such polynomial can be decomposed into a bounded number of multilinear polynomials all of which have extremely small eigenvalues. We use these new ingredients to give a deterministic algorithm for a Gaussian-space version of the approximate counting problem, and then employ standard techniques for working with low-degree PTFs (invariance principles and regularity lemmas) to reduce the original approximate counting problem over the Boolean hypercube to the Gaussian version.