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

DOI10.1007/s00440-017-0804-yzbMath1398.60040OpenAlexW2757708033MaRDI QIDQ1656545

Rocco A. Servedio, Anindya De

Publication date: 10 August 2018

Published in: Probability Theory and Related Fields (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00440-017-0804-y

zbMATH Keywords

Malliavin calculusStein's methodpolynomialscentral limit theoremapproximate countingGaussian chaos

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (1)

Moments of Gaussian chaoses in Banach spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• DNF sparsification and a faster deterministic counting algorithm
• The correct exponent for the Gotsman-Linial conjecture
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• The sum of \(D\) small-bias generators fools polynomials of degree \(D\)
• Perceptrons of large weight
• Estimates of moments and tails of Gaussian chaoses
• Halfspace matrices
• A new method of normal approximation
• Fluctuations of eigenvalues and second order Poincaré inequalities
• Noise stability of functions with low influences: invariance and optimality
• Multivariate normal approximation using Stein's method and Malliavin calculus
• Central limit theorems for non-linear functionals of Gaussian fields
• The Frechet distance between multivariate normal distributions
• Majority gates vs. general weighted threshold gates
• On the second eigenvalue of hypergraphs
• On deterministic approximation of DNF
• The number of eigenvalues of a tensor
• The inverse Shapley value problem
• Every linear threshold function has a low-weight approximator
• Central limit theorems for sequences of multiple stochastic integrals
• Theory of majority decision elements
• Pseudorandom Generators for Polynomial Threshold Functions
• Lectures on Gaussian Approximations with Malliavin Calculus
• Bounding the average sensitivity and noise sensitivity of polynomial threshold functions
• Explicit Dimension Reduction and Its Applications
• Small-Bias Probability Spaces: Efficient Constructions and Applications
• Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
• Learning Kernel-Based Halfspaces with the 0-1 Loss
• Agnostically Learning Halfspaces
• Stein's method meets Malliavin calculus: a short survey with new estimates
• A fast and simple randomized parallel algorithm for the maximal independent set problem
• On the Size of Weights for Threshold Gates
• Gaussian Hilbert Spaces
• The Intersection of Two Halfspaces Has High Threshold Degree
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A Small PRG for Polynomial Threshold Functions of Gaussians
• An FPTAS for #Knapsack and Related Counting Problems
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)

This page was built for publication: A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting