A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting

• 成果类型: Article
• 署名作者: De, Anindya; Servedio, Rocco A.
• 署名单位: Northwestern University; Columbia University
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-017-0804-y
• 发表日期: 2018
• 页码: 981-1044
• 关键词: threshold functions; inequalities; dnf; eigenvalues; halfspaces; algorithm; weight

摘要

One of the main results of this paper is a new multidimensional central limit theorem (CLT) for multivariate polynomials under Gaussian inputs. Roughly speaking, the new CLT shows that any collection of Gaussian polynomials with small eigenvalues (suitably defined) must have a joint distribution which is close to a multidimensional Gaussian distribution. The new CLT is proved using tools from Malliavin calculus and Stein's method. A second main result of the paper, which complements the new CLT, is a new decomposition theorem for low-degree multilinear polynomials over Gaussian inputs. Roughly speaking, this result shows that (up to some small error) any such polynomial is very close to a polynomial which can be decomposed into a bounded number of multilinear polynomials all of which have extremely small eigenvalues. An important feature of this decomposition theorem is the delicate control obtained between the number of polynomials in the decomposition versus their eigenvalues. As the main application of these results, we give a deterministic algorithm for approximately counting satisfying assignments of a degree-d polynomial threshold function (PTF) over the domain ; this is a well-studied problem from theoretical computer science. More precisely, given as input a degree-d polynomial over and a parameter , the algorithm approximates to within an additive in time . (Since it is NP-hard to determine whether the above probability is nonzero, any sort of efficient multiplicative approximation is almost certainly impossible even for randomized algorithms.) Note that the running time of the algorithm (as a function of , the number of coefficients of a degree-d PTF) is a fixed polynomial. The fastest previous algorithm for this problem (Kane, CoRR, 2012), based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time for all c > 0.