A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting (Q1656545): Difference between revisions

The first main contribution of the present paper is a multidimensional central limit theorem for \(r\)-tuples \((p_1(x),\ldots,p_r(x))\) of degree \(d\) polynomials with Gaussian input, which states that if each \(p_i\) has `small eigenvalues' (for a suitable definition), then the joint distribution of this \(r\)-tuple converges to a Gaussian distribution over \(\mathbb{R}^r\). The starting point of the proof is a central limit theorem in a well-known recent work combining Stein's method and Malliavin calculus (see, for example, [\textit{I. Nourdin} et al., Ann. Inst. Henri Poincaré, Probab. Stat. 46, No. 1, 45--58 (2010; Zbl 1196.60035)]). The proof also employs a geometry-preserving isomorphism between the space of symmetric tensors and multivariate Gaussian polynomials, allowing the authors access to tools and techniques from tensor algebra. A second main contribution is a decomposition theorem for low-degree multilinear polynomials with Gaussian input, showing that (up to some small error term) any such polynomial may be approximated by a polynomial which may be decomposed into a bounded number of multilinear polynomials which each have small eigenvalues (in the sense of the above central limit theorem). This result requires a careful balancing of the number of polynomials in the decomposition and the size of their eigenvalues. The above two results are applied to an approximate counting problem. Given a degree \(d\) polynomial \(p:\{-1,1\}^n\mapsto\mathbb{R}\) and an accuracy parameter \(\varepsilon>0\), the authors give a deterministic algorithm which outputs a value \(\tilde{v}\) such that \(|\tilde{v}-Pr(p(X)\geq0)|\leq\varepsilon\), where \(X\) is uniformly distributed over \(\{-1,1\}^n\). This algorithm runs in time \(O_{d,\varepsilon}(1)\cdot\text{poly}(n^d)\), better than previously known algorithms.