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

2 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

Funding

Anindya De: Work was partly done while the author was hosted by Oded Regev at NYU and partly while the author was a fellow at the Simons Institute, Berkeley. Partly supported by NSF Grant CCF-1320188. Rocco A. Servedio: Supported by NSF Grants CCF-1115703 and CCF-1319788. We thank Ilias Diakonikolas for his contributions in the early stages of this project. We also thank Rafal Latala, Michel Ledoux, Elchanan Mossel, Ivan Nourdin and Krzysztof Oleszkiewicz for answering questions about the CLT. Part of this work was done when A.D. was hosted by Oded Regev and the Simons Institute. A.D. would like to thank them for their kind hospitality and support. Anindya De: Work was partly done while the author was hosted by Oded Regev at NYU and partly while the author was a fellow at the Simons Institute, Berkeley. Partly supported by NSF Grant CCF-1320188. Rocco A. Servedio: Supported by NSF Grants CCF-1115703 and CCF-1319788.

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