Noise stability of functions with low influences: invariance and optimality

DOI10.4007/ANNALS.2010.171.295zbMATH Open1201.60031arXivmath/0503503OpenAlexW2078929687WikidataQ62111467 ScholiaQ62111467MaRDI QIDQ974039FDOQ974039

Ryan O'Donnell, Elchanan Mossel, Krzysztof Oleszkiewicz

Publication date: 27 May 2010

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

Abstract: In this paper we study functions with low influences on product probability spaces. The analysis of boolean functions with low influences has become a central problem in discrete Fourier analysis. It is motivated by fundamental questions arising from the construction of probabilistically checkable proofs in theoretical computer science and from problems in the theory of social choice in economics. We prove an invariance principle for multilinear polynomials with low influences and bounded degree; it shows that under mild conditions the distribution of such polynomials is essentially invariant for all product spaces. Ours is one of the very few known non-linear invariance principles. It has the advantage that its proof is simple and that the error bounds are explicit. We also show that the assumption of bounded degree can be eliminated if the polynomials are slightly ``smoothed; this extension is essential for our applications to ``noise stability-type problems. In particular, as applications of the invariance principle we prove two conjectures: the ``Majority Is Stablest conjecture from theoretical computer science, which was the original motivation for this work, and the ``It Ain't Over Till It's Over conjecture from social choice theory.

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

Recommendations

• Robust optimality of Gaussian noise stability
• An integral inequality and its application to a problem of stabilization by noise
• Noise stability is computable and approximately low-dimensional
• scientific article; zbMATH DE number 7140483
• On quantitative noise stability and influences for discrete and continuous models
• Propagating Lyapunov functions to prove noise-induced stabilization
• A multidimensional version of noise stability
• On stabilization of partial differential equations by noise
• Noise stability and correlation with half spaces
• Stabilization of partial differential equations by noise

zbMATH Keywords

invariance principlemultilinear polynomialsboolean functions

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)
• Title not available (Why is that?)
• Inequalities in Fourier analysis
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Gaussian Hilbert Spaces
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• On the hardness of approximating minimum vertex cover
• Boolean functions with low average sensitivity depend on few coordinates
• On Russo's approximate zero-one law
• Every monotone graph property has a sharp threshold
• On the distribution of the Fourier spectrum of Boolean functions
• On the hardness of approximating Multicut and Sparsest-Cut
• Title not available (Why is that?)
• On the power of unique 2-prover 1-round games
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Title not available (Why is that?)
• Noise sensitivity of Boolean functions and applications to percolation
• Limit theorems for polylinear forms
• An isoperimetric inequality on the discrete cube and an elementary proof of the isoperimetric inequality in Gauss space
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Sobolev inequalities, the Poisson semigroup, and analysis on the sphere Sn.
• A Noncompact Choquet Theorem
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• On the Fourier tails of bounded functions over the discrete cube
• Gowers uniformity, influence of variables, and PCPs
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• Sharp thresholds of graph properties, and the $k$-sat problem
• A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
• Intersecting Families are Essentially Contained in Juntas
• Approximation resistant predicates from pairwise independence
• Positivity improving operators and hypercontractivity
• Influences of variables and threshold intervals under group symmetries
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• Harmonic analysis and Boolean function complexity
• Towards Sharp Inapproximability for Any 2-CSP
• How much are increasing sets positively correlated?
• Title not available (Why is that?)
• Graph products, Fourier analysis and spectral techniques
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• On the Rate of Convergence in the Limit Theorem for Quadratic Forms
• Hypercontractivity of simple random variables
• Note on the Berry-Esseen Theorem
• On the optimality of the random hyperplane rounding technique for MAX CUT
• Title not available (Why is that?)
• The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• Lectures on probability theory. Ecole d'Eté de Probabilités de Saint- Flour XXII-1992. Summer School, 9th-25th July, 1992, Saint-Flour, France
• Asymptotic expansions in non-central limit theorems for quadratic forms
• Limit Theorems for Multilinear Forms and Quasipolynomial Functions
• Conditional hardness for approximate coloring
• Social Indeterminacy
• A remark on quadrant normal probabilities in high dimensions
• Hypercontraction principle and random multilinear forms
• Lectures on probability theory and statistics. Ecole d'été de probabilités de Saint-Flour XXIV -- 1994. Lectures given at the summer school in Saint-Flour, France, July 7--23, 1994
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

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

This page was built for publication: Noise stability of functions with low influences: invariance and optimality

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q974039)