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

Anindya De*, Rocco A. Servedio

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

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 { - 1 , 1 } n; this is a well-studied problem from theoretical computer science. More precisely, given as input a degree-d polynomial p(x1, ⋯ , xn) over Rn and a parameter ϵ> 0 , the algorithm approximates Prx∼{-1,1}n[p(x)≥0]to within an additive ± ϵ in time Od , ϵ(1) · poly (nd). (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 nd, the number of coefficients of a degree-d PTF) is a fixed polynomial. The fastest previous algorithm for this problem (Kane, CoRR, arXiv:1210.1280, 2012), based on constructions of unconditional pseudorandom generators for degree-d PTFs, runs in time nOd,c(1)·ϵ-c for all c> 0.

Original languageEnglish (US)
Pages (from-to)981-1044
Number of pages64
JournalProbability Theory and Related Fields
Volume171
Issue number3-4
DOIs
StatePublished - Aug 1 2018

Keywords

  • Central limit theorem
  • Gaussian chaos
  • Malliavin calculus
  • Polynomials
  • Regularity lemma
  • Stein’s method

ASJC Scopus subject areas

  • Analysis
  • Statistics and Probability
  • Statistics, Probability and Uncertainty

Fingerprint Dive into the research topics of 'A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting'. Together they form a unique fingerprint.

Cite this