RECORD
Noise Sensitivity of Boolean Functions and Applications to Percolation
Probability · Submitted 26 Nov 1998
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on an $n+1$ by $n$ grid. A configuration is a function that assigns to every edge the value 0 or 1. Let $\omega$ be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges $e$ with $\omega(e)=1$. By duality, the probability for having a crossing is 1/2. Fix an $\epsilon\in(0,1)$. For each edge $e$, let $\omega'(e)=\omega(e)$ with probability $1-\epsilon$, and $\omega'(e)=1-\omega(e)$ with probability $\epsilon$, independently of the other edges. Let $p(\tau)$ be the probability for having a crossing in $\omega$, conditioned on $\omega'=\tau$. Then for all $n$ sufficiently large, $P\{\tau : |p(\tau)-1/2|>\epsilon\}<\epsilon$.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. | result 0.92 | 0.89 | 0.76 | asserted 1.00 |
| s1 | On the other hand, weighted majority functions are shown to be noise-stable. | result 0.98 | 0.88 | 0.11 | asserted 1.00 |
| s2 | Several necessary and sufficient conditions for noise sensitivity and stability are given. | contribution 0.73 | 0.90 | 0.11 | asserted 0.99 |
| s3 | Consider, for example, bond percolation on an $n+1$ by $n$ grid. | method 0.48 | 0.18 | 0.03 | unclear 0.86 |
| s4 | A configuration is a function that assigns to every edge the value 0 or 1. | background 0.58 | 0.11 | 0.02 | asserted 0.95 |
| s5 | Let $\omega$ be a random configuration, selected according to the uniform measure. | method 0.73 | 0.34 | 0.02 | asserted 0.94 |
| s6 | A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges $e$ with $\omega(e)=1$. | background 0.51 | 0.23 | 0.03 | asserted 0.91 |
| s7 | By duality, the probability for having a crossing is 1/2. | background 0.78 | 0.48 | 0.07 | asserted 1.00 |
| s8 | Fix an $\epsilon\in(0,1)$. | method 0.93 | 0.26 | 0.01 | unclear 0.82 |
| s9 | For each edge $e$, let $\omega'(e)=\omega(e)$ with probability $1-\epsilon$, and $\omega'(e)=1-\omega(e)$ with probability $\epsilon$, independently of the other edges. | method 0.98 | 0.41 | 0.03 | asserted 0.83 |
| s10 | Let $p(\tau)$ be the probability for having a crossing in $\omega$, conditioned on $\omega'=\tau$. | method 0.93 | 0.54 | 0.14 | asserted 0.53 |
| s11 | Then for all $n$ sufficiently large, $P\{\tau : |p(\tau)-1/2|>\epsilon\}<\epsilon$. | result 1.00 | 0.88 | 0.46 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of random errors gives almost no prediction whether the event occurs. On the other hand, weighted majority functions are shown to be noise-stable. Several necessary and sufficient conditions for noise sensitivity and stability are given. Consider, for example, bond percolation on an $n+1$ by $n$ grid. A configuration is a function that assigns to every edge the value 0 or 1. Let $\omega$ be a random configuration, selected according to the uniform measure. A crossing is a path that joins the left and right sides of the rectangle, and consists entirely of edges $e$ with $\omega(e)=1$. By duality, the probability for having a crossing is 1/2. Fix an $\epsilon\in(0,1)$. For each edge $e$, let $\omega'(e)=\omega(e)$ with probability $1-\epsilon$, and $\omega'(e)=1-\omega(e)$ with probability $\epsilon$, independently of the other edges. Let $p(\tau)$ be the probability for having a crossing in $\omega$, conditioned on $\omega'=\tau$. Then for all $n$ sufficiently large, $P\{\tau : |p(\tau)-1/2|>\epsilon\}<\epsilon$.
Human review
References
How the literature uses it
2 arXiv papers cite this in 2 sentences
Papers citing it
Cites it as background 2 papers
-
Average sensitivity [ref] and noise sensitivity [ref] are two fundamental quantities that arise in the analysis of Boolean functions.
Bounding the Sensitivity of Polynomial Threshold Functions · Background · 1.00
-
Noise sensitivity of Boolean functions introduced in the seminal works of [ref] , [ref] is an important notion in the analysis of Boolean functions.
An Invariance Principle for Polytopes · Results on Noise Sensitivity of Intersections of Halfspaces · 1.00
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.