Quantitative relation between noise sensitivity and influences

DOI10.1007/s00493-013-2719-2zbMath1299.05308arXiv1003.1839OpenAlexW2067570943MaRDI QIDQ2448963

Nathan Keller, Guy Kindler

Publication date: 5 May 2014

Published in: Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

Parseval identityinfluenceBoolean functionCauchy-Schwarz inequalityproduct measureFubini's theoremdiscrete cubebiased measureFourier-Walsh expansionnoise sensitiveTalagrand's lemma

Mathematics Subject Classification ID

Combinatorial probability (60C05) Boolean functions (06E30) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (12)

Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Talagrand inequality at second order and application to Boolean analysis ⋮ A simple reduction from a biased measure on the discrete cube to the uniform measure ⋮ Noise sensitivity in continuum percolation ⋮ Geometric influences. II: Correlation inequalities and noise sensitivity ⋮ Approximating the Noise Sensitivity of a Monotone Boolean Function ⋮ On Quantitative Noise Stability and Influences for Discrete and Continuous Models ⋮ Strong noise sensitivity and random graphs ⋮ On the correlation of increasing families ⋮ Fourier bounds and pseudorandom generators for product tests ⋮ When are sequences of Boolean functions tame? ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis

Cites Work

• Unnamed Item
• A simple reduction from a biased measure on the discrete cube to the uniform measure
• On the hardness of approximating minimum vertex cover
• Inequalities in Fourier analysis
• On Russo's approximate zero-one law
• On boundaries and influences
• How much are increasing sets positively correlated?
• A quantitative Arrow theorem
• On the Fourier tails of bounded functions over the discrete cube
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• Constant depth circuits, Fourier transform, and learnability
• On the noise sensitivity of monotone functions
• Some optimal inapproximability results
• Noise sensitivity of Boolean functions and applications to percolation

This page was built for publication: Quantitative relation between noise sensitivity and influences