Noise stability of functions with low influences: invariance and optimality

DOI10.4007/annals.2010.171.295zbMath1201.60031arXivmath/0503503OpenAlexW2078929687WikidataQ62111467 ScholiaQ62111467MaRDI QIDQ974039

Ryan O'Donnell, Elchanan Mossel, Krzysztof Oleszkiewicz

Publication date: 27 May 2010

Published in: Annals of Mathematics. Second Series (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/math/0503503

zbMATH Keywords

invariance principle multilinear polynomials boolean functions

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Functional limit theorems; invariance principles (60F17)

Related Items

A sprinkled decoupling inequality for Gaussian processes and applications, Forbidden intersections for codes, Fluctuations in Salem-Zygmund almost sure central limit theorem, Scaling limits of directed polymers in spatial-correlated environment, On the complexity of binary polynomial optimization over acyclic hypergraphs, Hypercontractivity on the symmetric group, Mathematics of computation through the lens of linear equations and lattices, Interactions of computational complexity theory and mathematics, Unnamed Item, A Peccati-Tudor type theorem for Rademacher chaoses, Biased halfspaces, noise sensitivity, and local Chernoff inequalities, Lipschitz bijections between boolean functions, On aggregation for heavy-tailed classes, Boolean functions: influence, threshold and noise, Bounds on 2-query locally testable codes with affine tests, The two-dimensional continuum random field Ising model, Berry-Esseen bounds and multivariate limit theorems for functionals of Rademacher sequences, Approximating CSPs Using LP Relaxation, Making the Long Code Shorter, Classical and free fourth moment theorems: universality and thresholds, Inapproximability of maximum biclique problems, minimum \( k\)-cut and densest at-least-\( k\)-subgraph from the small set expansion hypothesis, Gaussian bounds for noise correlation of functions, Standard simplices and pluralities are not the most noise stable, The continuum disordered pinning model, An orthogonal basis for functions over a slice of the Boolean hypercube, Complexity of approximating CSP with balance/hard constraints, Gaussian limits for subcritical chaos, Berry-Esseen bounds for functionals of independent random variables, Gaussian noise sensitivity and Fourier tails, A query efficient non-adaptive long code test with perfect completeness, A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting, Probabilistic view of voting, paradoxes, and manipulation, Solution of the propeller conjecture in \(\mathbb R^3\), A generalization of the Lindeberg principle, Low correlation noise stability of symmetric sets, Asymptotic existence of fair divisions for groups, Nonlocal Games with Noisy Maximally Entangled States are Decidable, A quantitative Arrow theorem, High-dimensional central limit theorems for homogeneous sums, PCPs via the low-degree long code and hardness for constrained hypergraph coloring, Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture, Combinatorics. Abstracts from the workshop held January 1--7, 2023, Hypercontractivity for global functions and sharp thresholds, Total variation distance between stochastic polynomials and invariance principles, A stability result for the cube edge isoperimetric inequality, Convergence in Law Implies Convergence in Total Variation for Polynomials in Independent Gaussian, Gamma or Beta Random Variables, Multidimensional limit theorems for homogeneous sums: A survey and a general transfer principle, Anticoncentration and Berry-Esseen bounds for random tensors, The critical 2d stochastic heat flow, Free energy of directed polymers in random environment in \(1+1\)-dimension at high temperature, Improved bounds for the total variation distance between stochastic polynomials, Noise correlation bounds for uniform low degree functions, Geometric influences, Anti-concentration Inequalities for Polynomials, Approximating the covariance ellipsoid, Fractional smoothness of distributions of polynomials and a fractional analog of the Hardy–Landau–Littlewood inequality, An invariance principle for the two-dimensional parabolic Anderson model with small potential, Stein's method in high dimensions with applications, High dimensional Hoffman bound and applications in extremal combinatorics, The probability of intransitivity in dice and close elections, A structure theorem for Boolean functions with small total influences, The Gaussian surface area and noise sensitivity of degree-\(d\) polynomial threshold functions, Invariance principles for homogeneous sums: universality of Gaussian Wiener chaos, Polynomial regression under arbitrary product distributions, Oded Schramm's contributions to noise sensitivity, Asymptotic independence of multiple Wiener-Itô integrals and the resulting limit laws, Invariance principles for homogeneous sums of free random variables, Universal Gaussian fluctuations on the discrete Poisson chaos, Geometric influences. II: Correlation inequalities and noise sensitivity, Global Cardinality Constraints Make Approximating Some Max-2-CSPs Harder, The correct exponent for the Gotsman-Linial conjecture, On Lipschitz Bijections Between Boolean Functions, Local minimality of the ball for the Gaussian perimeter, Noise stability of weighted majority, Three candidate plurality is stablest for small correlations, Kneser graphs are like Swiss cheese, Polynomial chaos and scaling limits of disordered systems, A bound on the Wasserstein-2 distance between linear combinations of independent random variables, Maximally stable Gaussian partitions with discrete applications, On the probability of a rational outcome for generalized social welfare functions on three alternatives, Unnamed Item, Hypercontractive inequality for pseudo-Boolean functions of bounded Fourier width, A tight quantitative version of Arrow's impossibility theorem, Higher order concentration for functions of weakly dependent random variables, Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems, On the Influences of Variables on Boolean Functions in Product Spaces, Moments of Gaussian chaoses in Banach spaces, The structure of Gaussian minimal bubbles, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Gaussian bounds for noise correlation of resilient functions, Online Submodular Maximization with Preemption, Lower bound on the correlation between monotone families in the average case, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, A tame sequence of transitive Boolean functions, Almost sure convergence on chaoses, On Khot’s unique games conjecture, When are sequences of Boolean functions tame?, The two-dimensional KPZ equation in the entire subcritical regime, The Quest for Strong Inapproximability Results with Perfect Completeness, The multivariate functional de Jong CLT, Harmonicity and invariance on slices of the Boolean cube, Remarks on Gaussian Noise Stability, Brascamp-Lieb and Slepian Inequalities, Rainbow Coloring Hardness via Low Sensitivity Polymorphisms, An invariance principle under the total variation distance, Common Information, Noise Stability, and Their Extensions, Some applications of hypercontractive inequalities in quantum information theory, Robust dimension free isoperimetry in Gaussian space

Cites Work