Noise sensitivity of Boolean functions and applications to percolation
From MaRDI portal
Publication:5932371
DOI10.1007/BF02698830zbMath0986.60002arXivmath/9811157MaRDI QIDQ5932371
Itai Benjamini, Gil Kalai, Oded Schramm
Publication date: 23 May 2002
Published in: Publications Mathématiques (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/math/9811157
Related Items (90)
Which properties of a random sequence are dynamically sensitive? ⋮ Percolation of the excursion sets of planar symmetric shot noise fields ⋮ Denseness of volatile and nonvolatile sequences of functions ⋮ Exceptional times of the critical dynamical Erdős-Rényi graph ⋮ Biased halfspaces, noise sensitivity, and local Chernoff inequalities ⋮ Uniform-distribution attribute noise learnability ⋮ Lipschitz bijections between boolean functions ⋮ Monotone Boolean formulas can approximate monotone linear threshold functions ⋮ Boolean functions: influence, threshold and noise ⋮ Noise-stability and central limit theorems for effective resistance of random electric networks ⋮ Spatial networks and percolation. Abstracts from the workshop held January 17--23, 2021 (hybrid meeting) ⋮ Noise sensitivity for the top eigenvector of a sparse random matrix ⋮ Annealed scaling relations for Voronoi percolation ⋮ Volatility of Boolean functions ⋮ Learning juntas in the presence of noise ⋮ Upper bounds on Fourier entropy ⋮ Computing Boolean functions from multiple faulty copies of input bits ⋮ Probabilistic view of voting, paradoxes, and manipulation ⋮ Learning intersections and thresholds of halfspaces ⋮ Pivotal, cluster, and interface measures for critical planar percolation ⋮ The sharp phase transition for level set percolation of smooth planar Gaussian fields ⋮ The inverse Shapley value problem ⋮ Quenched Voronoi percolation ⋮ The Fourier spectrum of critical percolation ⋮ Hypercontractivity for global functions and sharp thresholds ⋮ On the hardness of learning intersections of two halfspaces ⋮ Noise sensitivity of percolation via differential inequalities ⋮ Phase transitions and noise sensitivity on the Poisson space via stopping sets and decision trees ⋮ Noise sensitivity and stability of deep neural networks for binary classification ⋮ Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions ⋮ Exceptional times when the KPZ fixed point violates Johansson's conjecture on maximizer uniqueness ⋮ From stability to chaos in last‐passage percolation ⋮ On the \(\Phi \)-stability and related conjectures ⋮ Simulation example of a black noise ⋮ Noise correlation bounds for uniform low degree functions ⋮ Fractal iso-contours of passive scalar in two-dimensional smooth random flows ⋮ Interactions of computational complexity theory and mathematics ⋮ Noise sensitivity and exceptional times of transience for a simple symmetric random walk in one dimension ⋮ Scaling limits for the threshold window: when does a monotone Boolean function flip its outcome? ⋮ Bargmann-Fock percolation is noise sensitive ⋮ The Argument Against Quantum Computers ⋮ Exclusion sensitivity of Boolean functions ⋮ Noise sensitivity of critical random graphs ⋮ A simple reduction from a biased measure on the discrete cube to the uniform measure ⋮ On a biased edge isoperimetric inequality for the discrete cube ⋮ Polynomial regression under arbitrary product distributions ⋮ Unnamed Item ⋮ Oded Schramm's contributions to noise sensitivity ⋮ On the scaling limits of planar percolation ⋮ Noise sensitivity in continuum percolation ⋮ Quantitative relation between noise sensitivity and influences ⋮ 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 ⋮ Fourier analysis and large independent sets in powers of complete graphs ⋮ On the four-arm exponent for 2D percolation at criticality ⋮ Noise stability of weighted majority ⋮ Corner percolation on \(\mathbb Z^{2}\) and the square root of 17 ⋮ Noise stability and correlation with half spaces ⋮ Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality ⋮ Noise sensitivity and Voronoi percolation ⋮ Partially Observed Boolean Sequences and Noise Sensitivity ⋮ Noise sensitivity of Boolean functions and applications to percolation ⋮ On the sensitivity to noise of a Boolean function ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ Quantitative noise sensitivity and exceptional times for percolation ⋮ Robust optimality of Gaussian noise stability ⋮ Subcritical $\mathcal {U}$-bootstrap percolation models have non-trivial phase transitions ⋮ Hardness amplification within NP ⋮ Local time on the exceptional set of dynamical percolation and the incipient infinite cluster ⋮ Strong noise sensitivity and random graphs ⋮ The annealed spectral sample of Voronoi percolation ⋮ On the correlation of increasing families ⋮ A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry ⋮ Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity ⋮ A tame sequence of transitive Boolean functions ⋮ On the rate of convergence in quenched Voronoi percolation ⋮ Edge-isoperimetric inequalities and ball-noise stability: linear programming and probabilistic approaches ⋮ \(\mathcal{U}\)-bootstrap percolation: critical probability, exponential decay and applications ⋮ When are sequences of Boolean functions tame? ⋮ Dynamical noise sensitivity for the voter model ⋮ Linear transformations of monotone functions on the discrete cube ⋮ Noise sensitivity of the top eigenvector of a Wigner matrix ⋮ Percolation of three fluids on a honeycomb lattice ⋮ Learning DNF from random walks ⋮ On the ``majority is least stable conjecture ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis ⋮ Unnamed Item ⋮ Convergence towards an asymptotic shape in first-passage percolation on cone-like subgraphs of the integer lattice ⋮ Reed-Muller Codes
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The average sensitivity of bounded-depth circuits
- On the power of small-depth threshold circuits
- Inequalities in Fourier analysis
- Boolean functions with low average sensitivity depend on few coordinates
- Conformal invariance of Voronoi percolation
- On Russo's approximate zero-one law
- Influences of variables and threshold intervals under group symmetries
- Dynamical percolation
- The influence of variables in product spaces
- Scaling relations for 2D-percolation
- Strict inequalities for some critical exponents in two-dimensional percolation
- Spectral densities describing off-white noises
- Concentration of measure and isoperimetric inequalities in product spaces
- How much are increasing sets positively correlated?
- Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
- Constant depth circuits, Fourier transform, and learnability
- Harmonic Analysis of Polynomial Threshold Functions
- Polynomial Threshold Functions, $AC^0 $ Functions, and Spectral Norms
- A note on percolation
- Percolation Probabilities on the Square Lattice
- Sharp thresholds of graph properties, and the $k$-sat problem
- Conformal invariance in two-dimensional percolation
- Every monotone graph property has a sharp threshold
- Noise sensitivity of Boolean functions and applications to percolation
This page was built for publication: Noise sensitivity of Boolean functions and applications to percolation
