{'fraction_non_alphanumeric': 0.06247575278283446, 'fraction_numerical': 0.021024202453072308, 'mean_word_length': 3.5264757530730786, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 79, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Noise Sensitivity in Continuum Percolation

We prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality. This is the first such result for a Continuum Percolation model, and the first for which the critical probability p_c \ne 1/2. Our proof uses a version of the Benjamini-Kalai-Schramm Theorem for biased product measures. A quantitative version of this result was recently proved by Keller and Kindler. We give a simple deduction of the non-quantitative result from the unbiased version. We also develop a quite general method of approximating Continuum Percolation models by discrete models with p_c bounded away from zero; this method is based on an extremal result on non-uniform hypergraphs.


Introduction
The concept of noise sensitivity of a sequence of Boolean functions was introduced in 1999 by Benjamini, Kalai and Schramm [9], and has since developed into one of the most exciting areas in Probability Theory, linking Percolation with Discrete Fourier Analysis and Combinatorics. So far, most attention has been focused on percolation crossings in two dimensions [9,21,34], either for bond percolation on the square lattice Z 2 , or for site percolation on the triangular lattice T. In this paper we study the corresponding questions in the setting of Continuum Percolation; in particular, we shall prove that the Poisson Boolean model, also known as the Gilbert disc model, is noise sensitive at criticality.
Roughly speaking, a sequence of Boolean functions f n : {0, 1} n → {0, 1} is said to be noise sensitive if a slight perturbation of the state ω asymptotically causes all information about f n (ω) to be lost. More precisely, let ε > 0 and suppose that ω ∈ {0, 1} n is chosen uniformly at random. Define ω ε ∈ {0, 1} n to be the (random) state obtained by re-sampling each coordinate (independently and uniformly) with probability ε, and note that ω ε is also a uniform element of {0, 1} n . Then the sequence (f n ) n 1 is said to be noise sensitive (NS) if, for every ε > 0, For example, the Majority function (f n (ω) = 1 iff ω j > n/2) and the Dictator function (f n (ω) = 1 iff ω 1 = 1) are not noise sensitive, but the Parity function (f n (ω) = 1 iff ω j Since f G N is defined on a continuous state space, we shall need to modify the definition of noise sensitivity. Let ε > 0 and λ > 0, and let η ⊂ R 2 be chosen according to a Poisson point process of intensity λ. We shall denote the measure associated to this Poisson process by P λ , expectation with respect to this measure by E λ , and variance Var λ . We define η ε to be the random subset of R 2 obtained by deleting each element of η independently with probability ε, and then adding a independent Poisson point process of intensity ελ. It is clear that η ε has the same distribution as η, and we will for that reason allow a minor abuse of notation letting P λ denote the measure by which the pair (η, η ε ) is chosen.
Definition 1 (Noise sensitivity for Continuum Percolation). We say that the Poisson Boolean model is noise sensitive at λ if the sequence of functions (f G N ) N 1 satisfies lim We shall say that the model is noise sensitive at criticality if it is noise sensitive at λ c .
We remark that the Poisson Boolean model is trivially noise sensitive at every λ = λ c . The reason is simply that when λ > λ c (or λ < λ c ), then lim N f G N = 1 a.s. (or lim N f G N = 0 a.s.), as is well known.
The following theorem is our main result. It is the analogue for the Poisson Boolean model of the result from [9] mentioned above concerning bond percolation on Z 2 . Theorem 1.1. The Poisson Boolean model is noise sensitive at criticality.
The proof of Theorem 1.1 is based on two very general theorems, neither of which uses any properties of the specific model which we are studying. The first is a generalization of one of the main theorems of Benjamini, Kalai and Schramm [9], a result referred to as the BKS Theorem, to biased product measures. It gives a sufficient condition (based on the concept of influence) for an arbitrary sequence of functions to be noise sensitive at density p (see Theorem 1.2). A quantitative version of the BKS Theorem for biased product measures was recently proved by Keller and Kindler [28]. Their result is therefore a strengthening of the qualitative result of [9]. We shall give a short deduction of the BKS Theorem for general p ∈ (0, 1) from the uniform case.
The second main tool is an extremal result on arbitrary non-uniform hypergraphs (i.e., arbitrary events on {0, 1} n ), which allows us to bound the variance that arises when two stages of randomness are used to choose a random subset. We shall use this bound (see Theorem 1.4) to prove noise sensitivity for the Poisson Boolean model via a corresponding result for a particular discrete percolation model (see Theorem 1.3). These tools are quite general, and we expect both to have other applications; we shall therefore state them here, and in some detail, for easy reference.
In order to state the BKS Theorem for product measure, we first need to define noise sensitivity in this setting. Let P p denote product measure with density p ∈ (0, 1) on {0, 1} n , i.e., P p (ω i = 1) = p independently for every i ∈ [n] := {1, 2, . . . , n}. (We will let E p denote expectation with respect to this measure.) When p = 1/2 this corresponds to picking an element of {0, 1} n uniformly at random, and so we refer to it as the uniform case. Define ω ε as above, by re-randomizing each bit independently with probability ε. Definition 2 (Noise sensitivity at density p). A sequence of functions f n : {0, 1} n → [0, 1] is said to be noise sensitive at density p (NS p ) if, for every ε > 0, When p = 1/2, this is equivalent to (1), the definition of noise sensitivity from [9].
The influence at density p, denoted Inf p,i (f ), of a coordinate i ∈ [n] in a function f : {0, 1} n → [0, 1], is defined by where σ i is the function that flips the value of ω at position i. We denote the sum of the squares of the influences of f by Inf p,i (f ) 2 .
The following theorem was first proved by Benjamini, Kalai and Schramm [9] in the case p = 1/2, but also remarked to hold for general p. A quantitative version was obtained by Keller and Kindler [28]. The result was stated in [9] for functions into {0, 1}, but the proof works also for functions into [0, 1], as was also observed in [28, page 3]. We shall give a simple deduction of this theorem from the uniform case. We remark that the approach we use to prove Theorem 1.2 is quite general, and may be used to extend various other results from uniform to biased product measures, see Section 2.2. Before introducing our second main tool, Theorem 1.4, let us give some more context, by describing our general approach to the proof of Theorem 1.1.
We shall choose our Poisson configuration η ⊂ R 2 in two steps; in other words, we view the Poisson Boolean model as a 'weighted average' (according to a certain probability distribution) of a family of discrete percolation models. To be precise, for each countable set B ⊂ R 2 and p ∈ (0, 1) we consider the following simple model; it is nothing more than site percolation on the graph (with vertex set B) defined by the Poisson Boolean model. Definition 3 (The percolation model P B p ). For each countable B ⊂ R 2 and p ∈ (0, 1), a configuration η ⊂ B in the percolation model P B p is obtained by including each point of B independently with probability p.
A p-subset of a (countable) set S is a random subset chosen by including each element independently with probability p. We shall write P S p for the corresponding probability distribution; or just P p when S = [n]. We will be interested in the P B p model for fixed (small) p > 0 in the case where B ⊂ R 2 is chosen according to P λc/p , the measure of a Poisson point process with intensity λ c /p. Given B chosen in that way, let η denote a p-subset of B. That is, choose η ⊂ B according to the conditional measure P B p . We emphasize that choosing η in this two-step procedure is equivalent to choosing it according to a Poisson point process of intensity λ c . Consequently, D(η) corresponds to a configuration of the occupied space in the Poisson Boolean model at criticality.
For Thus, the proof of Theorem 1.1 divides naturally into two parts. In the first we adapt the methods of Benjamini, Kalai and Schramm [9] to prove noise sensitivity of the discrete models P B p ; in the second we use our bound on the variance (Theorem 1.4, below) to prove that this noise sensitivity transfers to the continuous Poisson Boolean model. Interestingly, Theorem 1.4 will also be a key tool in the proof of Theorem 1.3.
To apply the adapted methods of [9], we require a bound on the fluctuations (in B chosen according to P λc/p ) of the probability of the crossing event in the model P B p ; we shall prove such a bound in a much more general context. Indeed, our next theorem holds for arbitrary hypergraphs (events), and thus we shall not use any properties of the specific percolation problem under consideration. By working at this level of generality, we are able to deduce, with no extra effort, similar bounds for crossings of rectangles, and for crossings in other percolation models.
A hypergraph H is simply a collection of subsets of [n]; or, equivalently, it is a subset of {0, 1} n . We call these sets 'edges', and remark that if every edge has exactly two elements then H is a graph. Given a hypergraph H, for each set B ⊂ [n] and p ∈ (0, 1) we define We remark that our use of the letter B here is supposed to be suggestive; in our applications it will correspond to a discrete approximation of the subset of R 2 considered above, which was chosen according to P λc/p . Indeed, given a rectangle R ⊂ R 2 , we shall discretize by partitioning it into n small squares. The set B will be a q-subset of [n], where q = q(n) is chosen so that (the set of centres of squares corresponding to) B has intensity λ c /p in R. Our hypergraph H will encode crossings of R in D(η), where η is a p-subset of these squares. Observe that in this case, if n is large, then r H (B, p) is very close to the probability of a crossing of R in the model P B p . Theorem 1.4. Let 0 < p 1/2, 0 < q < 1 and n ∈ N satisfy n 200(pqn) 3 , n 8p(qn) 2 and pqn 32 log 1 p . Let H be a hypergraph on vertex set [n], and let B be a q-subset of [n]. Then where the constant implicit on the right-hand side is independent of H.
We emphasize the crucial point, which is that our bound on Var q r H (B, p) goes to zero as p → 0 uniformly in H. Here, and throughout, f (x) = O(g(x)) denotes the existence of an absolute constant C > 0, independent of all other variables, such that |f (x)| C|g(x)| for every x in the domain of f and g. We remark that an alternative proof of Theorem 1.4 was recently obtained by one of us [2], using completely different methods.
As noted above, we shall use Theorem 1.4 in order to prove that the sequence (f B N ) N 1 is noise sensitive for P λc/p -almost every B, as well as to deduce Theorem 1.1 from Theorem 1.3. Indeed, we shall use Theorem 1.4 together with the 'deterministic algorithm' method (see Sections 2.3 and 5) to obtain bounds on the influences of variables; Theorem 1.3 then follows from the BKS Theorem for product measure.
We study in this paper how methods developed to study noise sensitivity for discrete percolation models can be adapted to a continuum setting. We have chosen to follow the approach of Benjamini, Kalai, and Schramm [9]. More recently, quantitative noise sensitivity has been introduced. Here one aims at determining the rate at which ε = ε(n) is allowed to decay while the limit in (1) persists. Results of this kind were obtained by Schramm and Steif [34] and Garban, Pete, and Schramm [21] in the context of percolation crossings on the square lattice Z 2 and triangular lattice T 2 . As a corollary of our main result (Theorem 1.1), via the approach developed in [34], it is possible to obtain similar quantitative results for the Poisson Boolean model.
Define the noise sensitivity exponent (for the Poisson Boolean model) as the supremum over the set of α 0 for which the limit in Definition 1 holds with ε = ε(N) = N −α .
Corollary 1.5. The noise sensitivity exponent for the Poisson Boolean model at criticality is strictly positive. That is, there exists α > 0 such that, for ε(N) = N −α , We shall, in Section 8, only outline the proof of Corollary 1.5. The rest of the paper is organized as follows. In Section 2 we give a full overview of the proof, and state several other results which may be of independent interest. In Section 3 we recall some facts about the Poisson Boolean model, and in Sections 4 and 5 we prove Theorem 1.2 and extend the deterministic algorithm method of [9] to general p ∈ (0, 1). In Section 6 we prove Theorem 1.4, and deduce some simple consequences, in Section 7 we prove Theorem 1.3 and deduce Theorem 1.1, and in Section 8 we sketch the proof of Corollary 1.5. Finally, in Section 9 we state some open questions.
Throughout the article we treat elements of {0, 1} n as subsets of [n], and vice versa, without comment, by identifying sets with their indicator functions. Thus P p denotes the biased product measure on {0, 1} n , and also the probability distribution associated with choosing a p-subset of [n]. As remarked above, we shall (suggestively) use the letter B to denote both a q-subset of [n], and a subset of R 2 chosen according to P λc/p (i.e., according to a Poisson point process with intensity λ c /p), and trust that this will not confuse the reader. The letter η will always denote a random subset of the plane, chosen according to a Poisson process of intensity λ c ; or, equivalently, chosen as a p-subset of the set B ⊂ R 2 .

Further results, and an overview of the proof
In this section we introduce a number of auxiliary methods and results that we shall use in the proof of Theorem 1.1, and which may also be of independent interest. In particular, we introduce a new way of deducing results for biased product measures from results in the uniform case. We shall use this method in Sections 4 and 5 to generalize the BKS Theorem and the deterministic algorithm method of Benjamini, Kalai and Schramm [9].
Let us begin by examining the link between the Poisson Boolean model and the model P B p . It is this link that will enable us to deduce Theorem 1.1 from Theorems 1.3 and 1.4. First, to illustrate the sense in which the Boolean model may be viewed as an 'average' of the discrete percolation models P B p , let us fix p ∈ (0, 1), and observe that where the second equality follows since if B ⊂ R 2 is chosen according to a Poisson point process of intensity λ c /p, then η is distributed as a Poisson point process of intensity λ c . Furthermore, it is not difficult to show that for ε ∈ (0, 1 − p) and ε ′ = ε/(1 − p) where, as the notation suggests, on the left-hand side (η, η ε ) is specified as in Definition 1, and on the right-hand side (η, η ε ′ ) is chosen as in Definition 2, as subsets of B (see Section 7). Thus, proving that the Poisson Boolean model is noise sensitive at criticality reduces to proving that (for some p) as N → ∞. Theorem 1.3 says exactly that, for fixed p, the first term is o(1) as N → ∞, while the following proposition shows that the second term can be made arbitrarily small by choosing p appropriately.
We shall deduce the proposition from Theorem 1.4 via a straightforward discretization argument. Since the expression in (5) in fact is independent of p (as seen in (4)), it follows that (5) holds (see Section 7 for more details).
Having described how we shall deduce Theorem 1.1 from Theorems 1.3 and 1.4, we continue this section with a few comments on their proofs, as well as a presentation of some results and methods we shall use for that purpose.
The proof of Theorem 1.4, given in Section 6, does not rely on the remainder of the paper, but follows instead from an inequality due to Bey [11] (see Section 2.4 for a brief overview). The proof of noise sensitivity in the P B p model (Theorem 1.3) is given in Section 7, and is based on the approach developed by Benjamini, Kalai, and Schramm [9]. Our main challenge will be to extend their method to the non-uniform case; in particular, we shall need to prove the BKS Theorem for biased product measure (Theorem 1.2), and to generalize a result linking the revealment of algorithms to the influence of bits (see Section 2.3). In order to do so, we introduce a new method for reducing problems for biased product measure to the uniform case. This method is introduced in Section 2.2; in Section 4 we use it to prove the BKS Theorem for product measure, and in Section 5 to complete the extension of the deterministic algorithm approach.
We begin by stating the key property of the Poisson Boolean model that we shall need.
2.1. Non-triviality of crossing probabilities. If the probability (in P λc ) of the crossing events H(η, R N , •) were trivial, in the sense that it converged to 0 or 1 as N → ∞, then Theorem 1.1 would itself be trivial. However, this is not the case. Further, one may deduce, using Theorem 1.4, that if p > 0 is sufficiently small, then with probability close to 1 (in P λc/p ) the same is true for the model P B p , see Proposition 2.3. This fact will be a vital tool in our proof of the noise sensitivity of this model, as it will allow us to bound the probability of the 'one-arm event' (see Section 2.3). Throughout R a×b denotes the rectangle with side lengths a and b, centred at the origin.
Theorem 2.2 (Alexander [4]). For every t > 0 there exists c = c(t) > 0 such that Theorem 2.2 is in fact a slight extension of [4,Theorem 3.4], but it follows by the same argument. For completeness, we shall sketch the proof in Section 3. From this bound, together with Theorem 1.4, we shall deduce the following bound (see Section 7). Proposition 2.3. For every t, γ > 0 there exist constants c ′ = c ′ (t) > 0 and p 0 = p 0 (t, γ) > 0 such that if p ∈ (0, p 0 ), then We next turn to one of the key new techniques we introduce in this paper.

2.2.
A new method for proving results for biased product measures. We outline here a new method for deducing results in the setting of a density p product measure from the uniform case (i.e., the case p = 1/2). The idea is the following. Rather than considering directly the function f : {0, 1} n → [0, 1] where {0, 1} n is endowed with density p product measure, we consider a related function h f : {0, 1} n → [0, 1] where {0, 1} n is endowed with uniform measure. This function h f is obtained from f by a smoothing (or averaging) operation. Assume for now that p 1/2. Given any function f : where Z ∈ {0, 1} n is obtained as a 2p-subset of X. More formally, independently of X, pick a 2p-subset Y of [n] (i.e., P(Y i = 1) = 2p for each i ∈ [n], all independently) and define Z as the coordinate wise product of X and Y , i.e., Observe that h f : {0, 1} n → [0, 1] and that if X is uniformly chosen, then Z is a p-subset of [n]; Assume from now on that X is uniformly chosen in {0, 1} n . By relating various parameters of f (Z) and h f (X), results about one may be deduced from results concerning the other. The connection between f and h f is given by the following proposition. In the interest of generality we state the proposition for all p ∈ (0, 1). For p > 1/2 we define Z as a p-subset containing X. Formally, we set . Following the standard convention, by f being monotone we mean that f (ω) f (ω ′ ) for every ω, ω ′ ∈ {0, 1} n such that ω j ω ′ j for every j ∈ [n]. Proposition 2.4. Let f : {0, 1} n → [0, 1] and p ∈ (0, 1), and setp = min{p, 1 − p}.
(i) If f is monotone then h f is monotone.
, and moreover equality holds if f is monotone.
Moreover, if p = 1/2 then this is also equivalent to lim n→∞ Var h fn = 0.
We remark that the random variables X and Z realize the maximal coupling between the uniform measure and product measure of density p on {0, 1} n , or similarly, between a uniformly chosen subset and a p-subset of [n].
Other reduction methods have previously been used for similar purposes. See e.g. [15,19,27,29] for results in this direction.
2.3. The deterministic algorithm method. In order to prove that (f B N ) N 1 is NS p for P λc/p -almost every B (Theorem 1.3), we shall use the 'algorithm method', which was also introduced by Benjamini, Kalai and Schramm [9] in the case p = 1/2. (We would like to thank Jeff Steif for pointing out to us that the approach in [9] can be synthesized in the way it is presented here.) Given a function f : where ω ∈ {0, 1} n is chosen according to P p . The revealment δ K (A, p) of A with respect to a set K ⊂ [n] is defined to be max{δ j (A, p) : j ∈ K}.
Using Theorem 1.2, we shall prove the following theorem, which generalizes the method of [9] to the non-uniform set-up.
Theorem 2.5. Let r ∈ N be fixed, and let (f n ) n 1 be a sequence of monotone functions If, for a fixed p ∈ (0, 1), we have We aim to apply Theorem 2.5 to deduce noise sensitivity in the (discrete) model P B p . For this we shall need to define a deterministic algorithm which determines f B N , and show that it has low revealment for most sets B (with respect to P λc/p ). The algorithm which we shall use is the continuum analogue of that used in [9]. Let η be a p-subset of B. Roughly speaking, we 'pour water' into the left-hand side of the square R N , and allow water to infiltrate the occupied space D(η). Thus, an element in B will be queried only if it becomes wet via a path in D(η) reaching from the left-hand side. For elements in the left half of R N we pour water into the right-hand side (see Section 7 for a precise definition).
It is easy to see that the probability that an element x ∈ B is queried by A is at most the probability of the corresponding 'one-arm event', i.e., the event that there is a path in D(η) from x to the boundary of a square centered therearound (for background on arm-events, see e.g. [14]). In the original Poisson Boolean model, a bound on this probability can be deduced from Theorem 2.2. However, in order to apply Theorem 2.5 we need a bound for the model P B p ; we obtain such a bound using Proposition 2.3. In order to apply Proposition 2.3, we simply surround each point x ∈ B ∩ R N by c log N disjoint annuli, and show that, with very high probability (in P λc/p ), at least half of them are 'good', in the sense that the probability (in P B p ) that there is a vacant loop around x is at least c ′′ , for some small constant c ′′ > 0. It will then follow that (for P λc/p -almost every B), every x ∈ B ∩ R N has probability at most N −δ (in P B p ) of being queried by A, when N is large (see Section 7).

2.4.
Hypergraphs. Theorem 1.4 provides a very general bound on the variance that arises in settings where two stages of randomness are used to select a random subset. The main step in the proof of Theorem 1.4 is to prove a variance bound (Proposition 6.1) for the case where the random sets A ⊂ B have fixed sizes m k. It is then relatively straightforward to deduce a corresponding bound on Var q r H (B, p) , and thus prove Theorem 1.4, by bounding other factors that might contribute towards the variance. These bounds are obtained using Chernoff's inequality (see Section 6).
We shall control Var X m (B k ) , where B k is a uniformly chosen k element subset of [n] and X m (B) = X m (B, H) counts the number of hypergraph edges of size m contained in B ⊂ [n], using the following theorem of Bey [11] concerning the sum of squares of degrees in hypergraphs. It generalized results of Ahlswede and Katona [3] and de Caen [17], and answered a question of Aharoni [1].
Let e(H) denote the number of edges in a hypergraph H, and, given a set T ⊂ [n], let d H (T ) denote the degree of T in H, i.e., the number of edges of H which contain T . The following result bounds the sum of the squares of the degrees over sets of size t in an muniform hypergraph, i.e., one in which all edges have size m. By convention, we let n k := 0 for k < 0 and k > n.
Bey's inequality (Bey [11]). Let H be an m-uniform hypergraph on n vertices, and let t ∈ [m]. Then To see how Bey's inequality is related to the variance of X m (B k ), observe that d H (T ) 2 counts the number of (ordered) pairs of edges of size m in H which both contain T . Thus, summing over t (with appropriate weights), we obtain an upper bound on E X m (B k ) 2 .

Non-triviality of the crossing probability at criticality
In this section we shall sketch the proof (from [4]) of Theorem 2.2, which says that at criticality, the probability of crossing a rectangle is bounded away from zero and one. The proof is based on the RSW Theorem for the Poisson Boolean model, which was proved by Roy [33] for the vacant space (see below), and by Alexander [4] for the occupied space.
Recall that P λ indicates that the configuration η ⊂ R 2 is chosen according to a Poisson process with intensity λ. Let V η, R, • denote the event that there is a vacant vertical crossing of R, i.e., a crossing using only points of R N \ D(η), and define V η, R, • (vertical crossing in D(η) ∩ R N ) and H η, R, • similarly.
Vacant RSW Theorem (Roy [33], see Theorem 4.2 of [30]). For every δ, t, λ > 0, there exists an ε = ε(δ, t, λ) > 0 such that the following holds for every a, b, c > 0 with c 3a/2. If We remark that this result was in fact proved in substantially greater generality: it holds for random radii, with arbitrary distribution on (0, r) (where r ∈ R + is arbitrary). Alexander [4] proved the corresponding statement for the occupied space (for fixed radii), and used this result to prove the following characterization. (a) There is almost surely an infinite occupied component.
The same holds true if 'occupied' is changed for 'vacant' throughout.
It follows immediately that there is no percolation at criticality for either the occupied or vacant space. Proof. A standard argument shows that P λ H η, R 3N ×N , • is a continuous function of λ, and so the set of λ ∈ R for which property (d) of Theorem 3.1 holds is an open set. Theorem 2.2 follows immediately from Corollary 3.2, together with the following slight extension of Theorem 3.1.
The proof of Theorem 3.3 is almost identical to that of Theorem 3.1; for completeness, we shall sketch the argument.
Sketch proof of Theorem 3.3. We shall prove only (a); part (b) follows by the same proof, except using the Occupied RSW Theorem [4, Theorem 2.1] in place of the Vacant RSW Theorem. We claim that our assumption implies property (d) in Theorem 3.1, and hence (by property (a) of the theorem) that D(η) percolates. We remark that the implication (d) ⇒ (a) in Theorem 3.1 follows by a straightforward Peierls-type argument.
We want to show that property (d) of Theorem 3.1 holds. It is not hard to show that by the Vacant RSW Theorem, applied with a = b = c = N. The latter implies that for each ε > 0 there exists N = N(ε) 1 such that Next, observe that for every N > 0 and k ∈ N, . . , B 3k , and consider the leftmost and rightmost pieces B j touched by a vertical path across R 3N ×N . The first follows because either an N ×N square (made up of B j 's) is crossed vertically, or a k−1 k N × N rectangle is crossed horizontally. The second follows because either a k+1 k N × N rectangle is crossed vertically, or an N × N square is crossed horizontally.

BKS Theorem for biased product measures
A tool that has turned out to be very useful in connection with the study of Boolean functions is discrete Fourier analysis. For ω ∈ {0, 1} n and i ∈ [n], we define In fact, it is easily seen that the set {χ p S } S⊂[n] forms an orthonormal basis for the set of functions f : {0, 1} n → R. We can therefore express such functions using the so-called Fourier-Walsh representation (see [32,36]): The following lemma was proved in [9] in the uniform case; its generalization to arbitrary (fixed) p is similarly straightforward.
Although our results hold for arbitrary p ∈ (0, 1), we shall prove them only for p 1/2, since this is the case we shall need in our applications. The proofs for p > 1/2 all follow in exactly the same way. From now on, we will not stress that S ⊂ [n] in the notation. Furthermore, when p = 1/2 we shall write χ S for χ p S andf (S) forf p (S).
and that , since this is zero whenever at least one of the coordinates {ω i : i ∈ S} is re-randomized, and one otherwise. By (11), it follows that from which both implications follow easily.
Recall from (6) The key fact, that the sequence (f n ) n 1 is NS p if and only if (h fn ) n 1 is NS, will follow directly from Lemma 4.1, together with the following result.
It is now straightforward to deduce Proposition 2.4 from Proposition 4.2.
Proof of Proposition 2.4. We shall assume that p 1/2; once again, the other case follows similarly. Let f : But if f is monotone, then f (Xξ) is also monotone in X for every ξ ∈ {0, 1} n . Thus (13) implies that h f is monotone, as required.
(ii) We next claim that By the definition, we have Now, if X i = 1, then Y i = 1 if and only if Z i = 1, and if X i = 0 then Z i = 0, so the right-hand side of (14) is equal to But given Z i , the value of X i is irrelevant to f (Z), so we have (with obvious notation X {i} c ) as required. Finally, note that the inequality in (15) be replaced by an equality when f is monotone. The BKS Theorem for biased product measures follows almost immediately from the uniform case, together with Proposition 2.4.
Proof of Theorem 1.2. Let (f n ) n 1 be a sequence of functions f n : {0, 1} n → [0, 1], let p ∈ (0, 1), and assume that II p (f n ) → 0 as n → ∞. We are required to show that (f n ) n 1 is NS p .
By Proposition 2.4(ii), we have and so II(h fn ) → 0 as n → ∞. By the BKS Theorem (i.e., Theorem 1.2 in the case p = 1/2), which was proved in [9], it follows that (h fn ) n 1 is NS. But, by Proposition 2.4(iii), we have (h fn ) n 1 is NS if and only if (f n ) n 1 is NS p . Hence (f n ) n 1 is NS p , as required.

The deterministic algorithm approach
In this section we shall prove Theorem 2.5, the uniform case of which was proved in [9]. We shall use the method of [9], together with Theorem 1.2 and some of the results from the previous section.
We need the following definition.
Throughout this section let X and Z be the random variables defined in Section 2.2, so X ∈ {0, 1} n is chosen uniformly, and Z ∈ {0, 1} n with Z i = X i Y i , where Y i is chosen according to product measure with density 2p. (We assume again for simplicity that p 1/2.) Theorem 2.5 will follow by combining the BKS Theorem with the following two propositions, of which in [9] the first was proved in the case p = 1/2, and the second was proved for p = 1/2 for functions taking values in {0, 1}. We shall generalize them to the biased setting.
Recall that the revealment δ K (A, p) of an algorithm with respect to a set K ⊂ [n] is defined to be max{δ j (A, p) : j ∈ K}, where δ j (A, p) = P p A queries coordinate j .
We begin by proving Proposition 5.1, which follows almost immediately from the uniform case, together with Proposition 2.4.
Proof of Proposition 5.1. The proposition was proved in [9, Corollary 3.2] in the case p = 1/2; we apply this result to the function h f . It follows that j∈K for some C > 0. Next, observe that Since f is monotone, we have Inf 1/2,j (h f ) = 2p · Inf p,j (f ), by Proposition 2.4, and so the result follows.
The proof of Proposition 5.2 will be based on the argument used in [9, Section 4], but modified to fit in the current setting. The strategy is roughly as follows: let V denote the set of coordinates queried by the algorithm. Then with high probability, V ∩ K is small enough so that M K (X) will (probably) be determined by the values of bits of X in K \ V . By a careful coupling, we can make these independent of the value of f , and thus E f (Z)M K (X) is small.
We shall use Chernoff's inequality; see, e.g., [5,Appendix A]. Let Bin(n, p) denote the binomial distribution with parameters n and p. Throughout the rest of the paper, ξ n,p will denote a binomially distributed random variable with parameters n ∈ N and p ∈ (0, 1).
We shall also use the following simple property of the binomial distribution, which follows by Stirling's formula.
Observation 5.3. There exists C > 0 such that for any n ∈ N, p ∈ (0, 1) and a ∈ N, We are now ready to prove Proposition 5.2.
Proof of Proposition 5.2. We assume as usual that p 1/2, and note that the proof for p > 1/2 is similar. Let f : {0, 1} n → [0, 1] and ∅ = K ⊂ [n] (if |K| = 0 then both sides are zero). We begin by defining our coupling; the purpose is to make the values of X i outside V independent of those inside.
We shall obtain the random variables X and Z, defined in (7), as follows. Let Z 1 ∈ {0, 1} K , Z 2 ∈ {0, 1} [n]\K and Z 3 , Z 4 ∈ {0, 1} n be such that P Z j i = 1 = p, independently for each i and j. Similarly, let W 1 ∈ {0, 1} K , W 2 ∈ {0, 1} [n]\K and W 3 ∈ {0, 1} n be independent of the Z j i , and such that independently for every i and j. Set X j i = max Z j i , W j i , and observe that for every i and j. Next, we describe how to use the X j i and Z j i to assign values to coordinates, depending on the order in which they are queried by A. Indeed, run the algorithm, and do the following: 1. If j ∈ K is queried, and is the k th element of K to have been queried by A, then set Z j := Z 1 k and X j := X 1 k . 2. If j ∈ K is queried, and is the k th element of [n] \ K to have been queried by A, then set Z j := Z 2 k and X j := X 2 k . 3. When the algorithm stops, let π : K \ V → [|K \ V |] be an arbitrary bijection, and for each j ∈ K \ V set Z j := Z 3 k and X j := X 3 k , where k = π(j). 4. Finally, let Z j := Z 4 j and X j := X 4 j for each j ∈ [n] \ (V ∪ K).
Note that X is chosen uniformly and Z according to the product measure with density p. Moreover, note that if Z i = 1 then X i = 1, so the coupling is as in (7), as claimed. Let V ⊂ [n] be the (random) set of coordinates which are queried by the algorithm, and note that V is independent of Z 3 and W 3 . We first show that the set V ∩ K is likely to be small. Indeed, we have and so, if we define Next we shall deduce that, with high probability, the difference between the number of 0s and 1s on V ∩ K is less than that on K \ V . Indeed, let S k := k j=1 (2X 1 j − 1) denote this difference on the first k coordinates of X 1 , and let T k := k j=1 (2X 3 j − 1) denote the same thing for X 3 . Let and let Before proving the claim, let's see how it implies the proposition. Set Q = B 1 ∪B 2 ∪B 3 c , and let F be the sigma-algebra generated by Z 1 , Z 2 and W 1 . Then by symmetry, since T |K\V | is equally likely to be positive or negative, and Q implies |T |K\V | | > |S |V ∩K| |. Thus by the claim, and since F determines f (Z), we have as required. Thus, it only remains to prove the claim, which follows easily using Chernoff's inequality. We have already shown that P(B 1 ) δ K (A, p) 1/3 , and so it will suffice to prove corresponding bounds for B 2 and B 3 ∩ B c 1 . The bound for B 2 follows using Chernoff and the union bound. Indeed, let t = |K|δ K (A, p) 2/3 , and recall that X 1 was chosen uniformly. Thus, by Chernoff's inequality, Finally, we shall bound the probability of B 3 ∩ B c 1 ; that is, the probability that |V ∩ K| t = |K|δ K (A, p) 2/3 and |T |K\V | | |K|δ K (A, p) 1/3 log n.

By Observation 5.3 and the union bound, we have
for some constant C 1 > 0 and every m 1. Since V is determined by the information in F , and since X 3 is uniformly distributed, we have where we in the second inequality used that on B c 1 , we have |K \ V | |K| − t 3|K|/4, assuming that t |K|/4 (since otherwise δ K (A, p) 1/8, and the proposition is trivial). This completes the proof of the claim, and hence of the proposition as well.
It is now easy to deduce Theorem 2.5. We shall use the following straightforward optimization lemma.
Lemma 5.4. If a 1 a 2 . . . a n > 0, then We are ready to prove Theorem 2.5.
Proof of Theorem 2.5. Let r ∈ N be fixed, and let (f n ) n 1 be a sequence of monotone functions f n : {0, 1} n → [0, 1]. For each n ∈ N, let A 1 , . . . , A r ∈ A * (f ) and let K 1 , . . . , K r be a partition of [n]. Let p ∈ (0, 1), and suppose that as n → ∞ for each i ∈ [r]. We shall show that II p (f n ) → 0 as n → ∞, and hence deduce, by Theorem 1.2, that (f n ) n 1 is NS p .
Choose C > 0 so that Propositions 5.1 and 5.2 both hold for C, and assume that n ∈ N is sufficiently large so that δ K i (A i , p) 1/3 log n 1/(2C) for each i ∈ [r]. To bound II p (f n ) = n j=1 Inf p,j (f n ) 2 from above, we shall first bound j∈K Inf p,j (f n ) for every K ⊂ [n], and then apply Lemma 5.4. Let us assume for simplicity that δ K i (A i , p) 1/n for some i ∈ [r]; the other case follows by an almost identical calculation.
Proof of claim. By Proposition 5.1, for every K ⊂ [n] we have

Moreover, by Proposition 5.2, for every i ∈ [r] and every
Note that x 1+ √ − log x is increasing on (0, 1/2), and recall that C δ , the claim follows.
Without loss of generality, assume that Inf p,1 (f n ) . . . Inf p,n (f n ), and apply Lemma 5.4 with c j = Inf p,j (f n ), and By the claim applied to K = [k], we have, for each k ∈ [n], and hence, writing C ′ = C 2 r/ min{p, 1 − p} 2 , since p is fixed and j as n → ∞, as claimed. Thus, by Theorem 1.2, (f n ) n 1 is NS p , as required.
We finish this section by proving the following closely related result, which was also proved in [9, Theorem 1.6] in the case p = 1/2 (and for functions into [0, 1]). In fact we shall not need it, but since it follows immediately from the uniform case and Proposition 2.4, and may be of independent interest, we include it for completeness.
Given E h(X)M K (X) .
In particular, Λ(h f ) = max Theorem 5.5. There exists a constant C > 0 such that, if f : {0, 1} n → [0, 1] is monotone and p ∈ (0, 1), then Proof. We apply the uniform case to the function h f . By Proposition 2.4, it follows that as required.

Hypergraphs
In this section we shall prove Theorem 1.4, which will allow us to bound the variance (in P λc/p ) of the probability of crossing a rectangle in the model P B p . Although one can think of all the results in this section in terms of events on the cube {0, 1} n , it will be convenient for us to use the language of hypergraphs. For background on Graph Theory, see [12].
Recall that a hypergraph H is just a collection of subsets of [n], which we refer to as the edges of H. We shall write H m for the m-uniform hypergraph contained in H, that is, the collection of edges with m elements, and recall that r H (B, p) := P B p A ∈ H , where A is a p-subset of B. Throughout this section, B will denote a q-subset of [n].
The proof of Theorem 1.4 is in two parts: first we shall prove the corresponding result for sets A and B of fixed size; then we shall deduce the result for p-and q-subsets.
6.1. The proof for sets of fixed size. Let us begin by informally illustrating the central idea with a simple example. Let G be a (large) graph with vertex set [n], and consider the restriction of G to a random subset S ⊂ [n] selected uniformly at random from the sets of size k. If k = 2 then the resulting graph G[S] will have density either 0 or 1, which will typically be quite far from the density of the original graph. However, once k is a large constant the density of G[S] is already unlikely to be far from the density of G. Indeed, it is elementary to bound the variance of this density. We remark that with a little extra effort, one could improve the upper bounds in Proposition 6.1 by a factor of β m = e(H m )/ n m . Since we shall not need such a strengthening, however, we leave the details to the reader. In order to keep the presentation simple, we also make no attempt to optimize the constant.
We shall use some straightforward relations between binomial coefficients in the proof of Proposition 6.1; we state them here for convenience. Observation 6.2. Let n, k, m, t be integers such that k m t 1 and n 3m 3 . Then Proof. For (a), note that both sides count the number of pairs of m-subsets of a fixed k-set; on the right-hand side we have partitioned according to their intersection. For (b) and (c) simply cancel common terms, and note that, for fixed m and t, as n → ∞. More careful calculation shows that n 3m 3 suffices.
We shall use Bey's inequality in order to prove the following lemma, from which Proposition 6.1 follows easily. Let Proof. Let α(H, t) := (e, f ) : e, f ∈ H and |e ∩ f | = t denote the number of pairs (e, f ) of edges of H such that |e ∩ f | = t. We first claim that k ) e,f ∈Hm  Cancelling common terms, we easily see that for each 1 t m k 2m Hence, Finally, by Observation 6.2(a). Combining (17), (18), (19) and (20), we obtain as required.
It is easy to deduce Proposition 6.1 from Lemma 6.3.
Proof of Proposition 6.1. We shall prove the claimed bound on Var X m (B k ) ; the second statement follows immediately from the first, since X m (B k ) = k m X m (B k ). The result is trivial for m k 48m, so we can assume that k 48m. (In fact we shall only use that k 4m.) First, note that by Lemma 6.3, and since n km/2, we have where Y t (k, m) = k 2m−t 2m−t m m t . We shall see that most of the weight of the Y t (k, m) is concentrated on terms with small t. We split into two cases, depending on the size of m.
We shall prove that Indeed, first note that since k − 2m k/2 and (t + 1)k 2k 6m 2 . This proves the first inequality in (22); for the second, observe that as claimed. By (21), we obtain Var X m (B k ) 8m k k m 2 .
Let a := 6m 2 /k , and observe that (23) holds whenever t a. Thus since Y a (k, m) k m 2 and a + 1 9m 2 /k. Moreover, it is immediate that By (21) where |B| denotes the size of the set B. The latter of the two terms can be controlled using Proposition 6.1 and Chernoff's inequality. The challenge will be the former term. To see, heuristically, why Var q E q r H (B, p) |B| should be small, note that |B| will roughly fluctuate by √ qn around its mean. This will influence the size of a p-subset A of B roughly by p √ qn. However, |A| will naturally vary by √ pqn which is much larger than p √ qn when p is small. Hence, conditioning on the size of B will not affect the size of A much, and should imply that the former term in (26) is small. We begin with the latter term in (26). The first step is to prove the result corresponding to Proposition 6.1 for fixed size k of B and a randomly chosen subset thereof. Indeed, given a hypergraph H on vertex set [n], a subset S ⊂ [n] of size k, and p ∈ (0, 1), observe that where ξ k,p ∼ Bin(k, p), as in the previous section. The following proposition is an easy consequence of Proposition 6.1. Proof. The result follows from Proposition 6.1 and Chernoff's inequality, since if m 2pk then the variance ofX m (B k ) is at most 96p, and the probability that ξ k,p > 2pk is at most 2e −pk/16 .
To spell it out, note that if p 1/2 and m 2pk, then m k, n 3m 3 and n km/2, and so, by Proposition 6.1, Since Var X m (B k ) 1, the same bound trivially holds for p > 1/2.
By Cauchy-Schwarz, we have Cov(X, Y ) Var(X)Var(Y ), and thus where the last step is by Chernoff's inequality, as required.
In order to deduce Theorem 1.4 from Proposition 6.4, we shall use the following simple bounds on binomial random variables, which follow immediately from Chernoff's inequality.
We shall also need the following bound, relating nearby binomial coefficients.
Sketch of proof. We claim that, for each k ℓ k ′ , Indeed, note that m pℓ + 6 pqn log 1 p , and so Now we simply take the product over ℓ and note that this range is at most of size 4 qn log(1/p), to obtain as required. The proof of the lower bound is the same.
We are now ready to prove Theorem 1.4.
For each k ∈ [n], let α k : is a uniformly chosen set of size k. Let K and K ′ be independent random variables, each with distribution Bin(n, q).
Proof of Claim 1. Applying the conditional variance formula we obtain as in (26) Var q r H (B, p) = Var E r H (B, p) |B| + n k=0 Var r H (B, p) |B| = k P ξ n,q = k .
Note that in the first term, the variance is over the choice of ℓ := |B|, and the expectation over the (uniform) choice of a set B of size ℓ. In the sum, the variance is over the uniform choice of a k-set B. Now, E r H (B, p) |B| = k = α k , so the first term may be re-written as For the sum, first note that P ξ n,q < 16 p log 1 p 2p, by Observation 6.5. On the other hand, P(ξ n,q > 2qn) 2 exp(−qn/16) 2p, by Chernoff. For k 2qn we have 24(pk) 3 192(pqn) 3 n and 2pk 2 8p(qn) 2 n, so if 16 p log 1 p k 2qn, then, by Proposition 6.4, we have Var r H (B k , p) = O(p), and the claim follows.
By Observation 6.5, the probability that qn − 2 qn log 1 p K, K ′ qn + 2 qn log 1 p is at least 1 − 4p. Hence, it will suffice to prove the following claim.
Claim 2: If qn − 2 qn log 1 p k k ′ qn + 2 qn log 1 p , then Proof of Claim 2. Note that and set S = m : |m − pqn| 4 pqn log(1/p) . We assume for simplicity that α k ′ α k ; the other case is the same. We have since, by Chernoff's inequality and the triangle inequality, P ξ k,p ∈ S +P ξ k ′ ,p ∈ S = O(p). Moreover, by Lemma 6.6, we have for every m ∈ S. We conclude that as required.
It is now easy to deduce Theorem 1.4 from Claims 1 and 2, and (27). Indeed, as required.
We end the section by noting a couple of easy consequences of Theorem 1.4. The first is a generalization, to an arbitrary event on {0, 1} n , of the method we shall use to deduce Proposition 2.3 from Theorem 2.2. It follows almost immediately from Theorem 1.4, via Chebychev's inequality. First, note that a p-subset of a q-subset of [n] is a pq-subset of [n]. In particular, Corollary 6.7. For every ε > 0 there exists p 0 = p 0 (ε) > 0 such that if p ∈ (0, p 0 ), r ∈ (0, p), and n ∈ N satisfy n 200(rn) 3 , n 8(rn) 2 /p and rn 32 log 1 p , then for every event (or hypergraph) H ⊂ {0, 1} n .
Proof. Given ε > 0, choose p 0 > 0 in accordance to Theorem 1.4 such that for all p < p 0 , and for all H. By Chebychev's inequality and (28), as required.
Finally, we state the following extremal result of hypergraphs, which may be of independent interest, and follows easily from Proposition 6.1. Say that a hypergraph H is δ-quasi monotone with respect to (k, m) if e ∈ H m : e ⊂ B 1 − δ k m for every B ∈ H k . Corollary 6.8. For each δ > 0, there exists C > 0 such that the following holds for every k, m ∈ N, and every n max{3m 3 , km/2}. If H is a δ-quasi monotone hypergraph with respect to (k, m), then either Proof. Note that E X m (B k ) = β m k m , and apply Chebychev, using Proposition 6.1 to bound the variance. The theorem follows with C = O(1/δ 2 ).

Proof of Theorem 1.1
In this section we shall put together the pieces, and prove Theorem 1.1. We shall first deduce Propositions 2.1 and 2.3 from Theorem 1.4; then we shall use the deterministic algorithm method to prove Theorem 1.3; finally we shall deduce Theorem 1.1.
Throughout this section, B will be chosen according to P λc/p , and η will be chosen according to the conditional measure P B p . Var λc/p P B p H(η, R a×b , •) = 0.
In order to apply Theorem 1.4 we need to construct a discrete probability space which closely approximates the continuous space with measure P λc/p on the rectangle R a×b . In order to do so, for each δ > 0 consider the lattice Λ = Λ δ a,b := R (a+2)×(b+2) ∩ δZ 2 , and set n = |Λ δ a,b |, the number of vertices of δZ 2 in the rectangle R (a+2)×(b+2) . (Note that we consider the rectangle R (a+2)×(b+2) because it contains all the points which can affect the event H(η, R a×b , •).) Let p > 0, set q = q(n) to be and note that pqn ≈ λ c ab. In this subsection, since we shall be dealing with both continuous and discrete probability spaces, we shall writeB ⊂ Λ to denote a q-subset of Λ andη ⊂B to denote a p-subset ofB. Recall that P Λ q and PB p denote the corresponding probability measures.
The following lemma is an immediate consequence of Theorem 1.4.
Lemma 7.2. For every p ∈ 0, 1 2 , if a = a(p), b = b(p) 1 are sufficiently large and δ = δ(a, b) > 0 is sufficiently small, then the following holds. Let Λ = Λ δ a,b , n = |Λ| and q > 0 be as defined in (29). Then Proof. We apply Theorem 1.4 to the hypergraph H which encodes crossings of the rectangle R a×b . That is, we identify the vertices of Λ = Λ δ a,b with the elements of [n], and set It only remains to check that the conditions of Theorem 1.4 are satisfied if δ is sufficiently small. To see this, simply note that, by our choice of q, we have that pqn = Θ(ab) and n/ab → ∞ as δ → 0.
In order to deduce Proposition 7.1, we need to provide a coupling between our two probability spaces -one discrete, the other continuous -which approximately maps the crossing event H(η, R a×b , •) onto H(η, R a×b , •). In fact this is easy: simply map each point of B into the ℓ ∞ -nearest point of Λ = Λ δ a,b , and take δ = δ(a, b) sufficiently small.
We define a bad event E δ a,b on subsets B ⊂ R 2 , by saying that E occurs if either of the following holds: (a) Two points of B lie in the same δ × δ square, i.e., |ψ −1 (y) ∩ B| > 1 for some y ∈ Λ δ a,b . (b) There exist x, y ∈ B with 2 − 2δ x − y 2 2 + 2δ. (c) There exist x ∈ B such that 1 − δ x − ∂R a×b 1 + δ, where ∂R a×b denotes the boundary of R a×b and the distance between a point and a set is defined in the canonical way. Observe that if E δ a,b does not occur, then the graphs naturally induced by the points of B andB are identical, and the vertices are in 1-1 correspondence. Hence, conditional on E δ a,b c , the events H(η, R a×b , •) and H(η, R a×b , •) have the same probability, in P B p and PB p respectively. The following lemma shows that, if δ is sufficiently small, then the coupling (B,B) has the desired properties. 1 and p > 0, there is δ 0 = δ 0 (a, b, p) > 0 such that for all δ ∈ (0, δ 0 ) Proof. The first inequality holds by the observations above, since if E δ a,b does not occur, then the graphs defined by the points of B andB are identical.
To bound P λc/p E δ a,b , we estimate the probabilities of (a), (b) and (c). For property (a), this is O(δ 2 ab/p 2 ), since each square has probability O(δ 4 /p 2 ) of containing at least two points of B, and there are O(ab/δ 2 ) such squares.
For property (b), it is O(δab/p 2 ). Informally, the reason is that two points uniformly distributed in R a×b has probability of order δ/(ab) of falling within the right distance of each other. Furthermore, since there are order (λ c ab/p) 2 pairs of points, we arrive at the claimed probability. It is not hard to make this argument precise.
For property (c), a similar argument shows that the probability is O(δab).
We can now easily deduce Proposition 7.1 from Lemmas 7.2 and 7.3.
Proof of Proposition 7.1. Let p > 0, and choose a, b 1 sufficiently large and δ ∈ (0, p 2 ) small enough for Lemma 7.2 to hold. Let n = |Λ δ a,b | and q > 0 be as described above. Then, by Lemmas 7.2 and 7.3, To see that the Water Algorithm determines f B N (η), simply note that an element x ∈ B is queried if and only if there is a path from the left edge of R N to D(x), using only points of D(η) ∩ R N +2 . Thus, if f B N (η) = 1 then the algorithm will find a horizontal path across R N in D(η) ∩ R N ; conversely, if f B N (η) = 0 then the algorithm will output zero, since A ∞ ⊂ η. We shall apply the Water Algorithm for the vertices in the right-hand half of R N +2 , and the * -Water Algorithm for those in the left-hand half. Define and recall that for fixed B ⊂ R 2 and v ∈ B ∩ K R N , The following lemma will allow us to apply Theorem 2.5.
Lemma 7.4. For every C > 0, there exists δ > 0 and p 0 = p 0 (C) > 0 such that if p ∈ (0, p 0 ), then In order to prove Lemma 7.4, we first partition R N +2 into (N + 2) 2 squares of sidelength 1 in the canonical way, and denote these squares by S 1 , . . . , S (N +2) 2 . Define A ℓ to be the annulus centred at the origin, and consisting of all points with ℓ ∞ -norm between ℓ and 2ℓ, and for each 1 i (N + 2) 2 , let A ℓ (S i ) denote A ℓ shifted to be concentric to S i . Let C A ℓ (S i ), η denote the (monotone decreasing) event that there is a loop of vacant space in A ℓ (S i ); equivalently, it is the event that there is no path between the two faces of A ℓ (S i ) using only points of D(η). Now, consider the t = ⌊log 4 (N/4)⌋ annuli A ℓ(1) (S i ), . . . , A ℓ(t) (S i ), where ℓ(j) = 4 j . Note that the distance between A ℓ(j) (S i ) and A ℓ(j+1) (S i ) is at least 2 for each j, so the events C A ℓ(j) (S i ), η) are independent.
The following lemma easily implies Lemma 7.4.
Lemma 7.5. For every C > 0, there exists δ > 0 and p 0 = p 0 (C) > 0 such that if p ∈ (0, p 0 ), then for every S i that intersects for every sufficiently large N ∈ N.
Proof of Lemma 7.5. First note that, for a given B and S i ⊂ K R N , if the event C A ℓ(j) (S i ), η occurs for some 1 j t, then no point v ∈ B ∩ S i will be queried by the algorithm A W . This follows because v ∈ K R N , so v is ℓ ∞ -distance at least N/2 from the left edge of R N .
Thus, by independence, Next, by Proposition 2.3 and the FKG inequality (together with the union bound) it follows that for any γ > 0, if p ∈ (0, p 0 ), then for all sufficiently large ℓ ∈ N, where c ′′ = (c ′ ) 4 and p 0 = p 0 (γ) > 0 are constants given by Proposition 2.3. Using (32), we have that if γ = γ(C) is sufficiently small, and N (hence also t) is sufficiently large, as required. Finally, if B is such that P B p C A ℓ(j) (S i ), η c ′′ for at least t/2 of the annuli A ℓ(j) (S i ), then for this B, for some (small) δ > 0. Combining (31), (33) and (34), it follows that as required.
It is now easy to deduce Lemma 7.4.
Proof of Lemma 7.4. Since there are exactly (N + 2) 2 /2 N 2 squares S i in K R N , it follows immediately from Lemma 7.5, and the union bound, that as required.
We can now deduce Theorem 1.3.
Proof of Theorem 1.3. We prove that for each sufficiently small p > 0, the model P B p is NS p for P λc/p -almost every B. To do so we must prove that the sequence of crossing functions (f B N ) N 1 is NS p for P λc/p -almost every B, for all sufficiently small p > 0. According to Lemma 7.4 and Borel-Cantelli, there are δ > 0 and p 0 such that for every p ∈ (0, p 0 ) we have P λc/p δ B∩K R N A W , p > N −δ for at most finitely many N = 1.
By symmetry, it follows that also δ B∩K L N A * W , p N −δ for at most finitely many values of N, with probability one, and hence as N → ∞, for P λc/p -almost every B. Since f B N is monotone, we may apply Theorem 2.5, which implies that (f B N ) N 1 is NS p with probability one, as required.
7.3. The Poisson Boolean model is noise sensitive. We are finally ready to deduce Theorem 1.1; as we remarked in Section 2, it follows easily from Theorem 1.3 and Proposition 2.1. The key observation is that the following two constructions are equivalent: (a) Pick η according to the measure P λc , construct η ε by deleting each element of η independently with probability ε, and add a new independent configuration picked according to the measure P ελc . We consider the pair (η, η ε ). (b) Pick B according to the measure P λc/p , and let η be a p-subset of B. Setting ε ′ = ε/(1 − p), construct η ε ′ by re-randomizing the second step with probability ε ′ , independently, for every v ∈ B. We consider the pair (η, η ε ′ ). It is easy to see that picking (η, η ε ) according to the first construction is equivalent to picking (η, η ε ′ ) according to the second construction.
Now, recall that f G N is the function, defined on subsets η of the plane R 2 , which encodes whether or not there is a horizontal crossing of R N in the occupied space D(η) ∩ R N . To prove the noise sensitivity of the Poisson Boolean model we must prove that for every ε > 0 where the pair (η, η ε ) is obtained by the first construction above.
Proof of Theorem 1.1. Fix ε > 0. We have, by the observations above, (37) Proposition 2.1 shows that the second term in (37) can be made arbitrarily small by taking p > 0 sufficiently small and N sufficiently large. Theorem 1.3 implies in turn that for small (but fixed) p > 0, the first term converges to 0 as N → ∞. Since (37) holds for every p > 0, it follows that the limit (36) holds, and, since ε > 0 was arbitrary, the Poisson Boolean model is noise sensitive at criticality, as claimed.
We observe that in the extremal case when ε = 1 − p, (37) reduces to . Thus, as an immediate consequence of Theorem 1.1 we obtain the following strengthening of Proposition 2.1. Apart from its independent interest, we shall use Corollary 7.6 in the next section to obtain a quantitative bound on the noise sensitivity exponent associated with the Poisson Boolean model.

Quantitative noise sensitivity
Several years after the introduction of noise sensitivity in [9], an important breakthrough was obtained by Schramm and Steif [34], who established a direct connection between revealment and the Fourier spectrum of a function via the use of randomized algorithms 2 . Recall Lemma 4.1, which shows that a sufficiently strong bound on the Fourier coefficients is enough to deduce noise sensitivity. We here outline how the 'randomized algorithm' method of [34] can be used to prove Corollary 1.5, and hence strengthen Theorem 1.1.
Let p = 1/2, and observe that, by Corollary 7.6, the final term in the right-hand side of (37) vanishes as N → ∞, and does not depend on ε. As a consequence, in order to prove Corollary 1.5 it suffices to show that there exists α > 0 such that, with ε(N) = N −α , In other words, we need to prove that the noise sensitivity exponent for the P B 1/2 model is (a.s.) bounded away from zero. In particular, this means that we do not need to extend the approach of [34] from the uniform case to the biased setting; Theorem 1.1 (via Corollary 7.6) does the job for us.
The randomized algorithm method is based on the following relation between Fourier coefficients of a function and the revealment of an algorithm. Proposition 8.1 (Schramm and Steif [34]). Let f : {0, 1} n → R be a function and let A be a randomized algorithm determining f . For every k ∈ [n] we have where f 2 denotes the L 2 -norm of f with respect to uniform measure.
We continue with a rough sketch of how Proposition 8.1 can be used to deduce (38), which in turn implies Corollary 1.5. We proceed as follows: 1. First define a suitable algorithm A to be used; in fact, it is straightforward to adapt the algorithm which was used in [34] to the continuum setting. Roughly speaking, the algorithm chooses a starting point uniformly at random from the middle third of the left-hand side of the square R N , and then investigates (in two stages) whether or not there is an occupied crossing of R N originating above the starting point, and whether or not there is one originating below it. 2. Partition R N +2 into n = (N + 2) 2 unit squares S 1 , . . . , S n , and observe that if the algorithm is to examine a point in B ∩ S i , then the exploration path from the starting point must reach S i . The probability that this occurs can be bounded by the probability of a one-arm event originating from the square S i . (Some care needs to be taken with squares within distance, say, N 1/2 of the boundary of R N , but this is easily adjusted for.) 3. For small p > 0, an estimate on the probability of the one-arm event was obtained in Lemma 7.5, based on Proposition 2.3. To estimate δ [n] (A, 1/2), we need to extend this statement to cover also p = 1/2. Note that Corollary 7.6 together with Chebychev's inequality gives a statement very similar to Proposition 2.3 (valid for all p ∈ (0, 1)), but for crossings of the square R N instead of the rectangle R N ×tN . Perhaps the easiest way to convince oneself that the statement holds also for rectangles, is to observe that there is nothing special about the choice of a square in our study of the sensitivity of crossings. Indeed, one may easily verify that the proof of Theorem 1.1 goes through (practically word for word) in the case where R N is replaced by R N ×tN . Consequently, Corollary 7.6 also holds for rectangles, and hence for every t > 0 there exists a constant c = c(t) > 0 such that, for every p ∈ (0, 1), lim N →∞ P λc/p P B p H(η, R N ×tN , •) ∈ (c, 1 − c) = 0.
A bound on the one-arm event centred around a unit square S i is now easily obtained for p = 1/2, exactly as in Lemma 7.5. 4. Using the union bound and the Borel-Cantelli lemma, we conclude (exactly as in Section 7.2) that there exists δ > 0 such that, for all but finitely many N, the following holds for P 2λc -almost every B: given any unit square S in R N , the probability (in P B 1/2 ) of the one-arm event centred around S is at most N −δ . 5. An upper bound on the revealment of the algorithm was in step 2 argued to be given by the (maximal) probability of the one-arm event around a unit square S i . It follows that there exists δ > 0 such that P 2λc δ B∩R N+2 (A, 1/2) > N −δ for at most finitely many N = 1.
6. Via Proposition 8.1, it follows that for each α < δ/2 for P 2λc -almost every B. 7. As is easily verified (see the proof of Lemma 4.1), the noise sensitivity exponent for a sequence of Boolean functions (f n ) n 1 is at least α if lim n→∞ 0<|S| n αfn (S) 2 = 0. Consequently, (39) implies that the noise sensitivity exponent for the sequence (f B N ) N 1 is at least δ/2, for P 2λc -almost every B. Thus, (38) holds.
By the observations above, this completes (the sketch of) the proof of Corollary 1.5.

Open problems
In this paper we have laid out a fairly general approach to the problem of proving noise sensitivity in models of Continuum Percolation, and we expect that our method could be extended to prove similar results in more general settings. In this section we shall state a few of these open problems. 9.1. More general Poisson Boolean models. The simplest extension of Theorem 1.1 would be to the Poisson Boolean model with (bounded) random radii. To obtain this model, let R > 0 and fix an (arbitrary) distribution µ R on (0, R). Now let η ⊂ R 2 be chosen according to a Poisson point process, and place a disc of radius r(x) on each vertex x ∈ η, where r(x) is chosen according to µ R , independently for each vertex. There are various ways to perturb a configuration in this model. One may leave the positions of the points unaffected, but re-randomize some of the radii, or add and remove a small proportion of the balls, much like in this paper. We have foremost the latter choice in mind. Indeed, for this model the only missing ingredient is an RSW Theorem for the occupied space.
Conjecture 9.1. For every R > 0 and µ R , the Poisson Boolean model with random radii chosen according to µ R is noise sensitive at criticality.
An alternative generalization would allow us to use an arbitrary shape S instead of a disc. Given such an S ⊂ R 2 , and a set η chosen according to a Poisson point process, place a copy of S on every point x ∈ η; that is, set D(η) = x∈η x + S. Conjecture 9.2. If S is bounded and simply connected, then the Poisson Boolean model for S is noise sensitive at criticality.
Of course, one could construct a much more general model, in which a random shape (of random size) is placed on each point in η. We suspect that such a model will also exhibit the same behaviour. The corresponding question for higher dimensions is likely to be much harder.
Question 1. Is the Poisson Boolean model noise sensitive at criticality in d dimensions?
9.2. Voronoi percolation. Given a set η ⊂ R 2 , the Voronoi tiling of η (see [14], for example) is constructed by associating each point of R 2 with the point of η closest to it. We call the set of points associated to x ∈ η in this way the Voronoi cell of x. In Voronoi percolation we choose a random subset of the cells, by colouring each blue with probability p, and say that the model percolates if there exists an unbounded component of blue space. Bollobás and Riordan [13] proved that if η is chosen according to P λ , then this model has critical probability 1/2.
Given a Voronoi tiling V of R 2 , let f V N : {0, 1} V N → {0, 1} be the function which encodes crossings of R N , where V N denotes the collection of cells which intersect R N . Say that Voronoi percolation is noise sensitive at criticality if (f V N ) N 1 is NS, almost surely (in P λ ).
Benjamini, Kalai and Schramm [9, Section 5] asked whether knowing the Voronoi tiling, but not the colouring, gives (a.s.) any information as to whether or not there exists a blue horizontal crossing of R N . We make the following, complementary conjecture. Conjecture 9.3. Voronoi percolation is noise sensitive at criticality.
Alternatively, one could define noise sensitivity by resampling the Poisson point process, as well as the colouring; we expect the corresponding result to hold for this definition also. 9.3. Stronger results for the Gilbert model. In Corollary 1.5 we show that it is possible to obtain quantitative estimates on how sensitive percolation crossings are to noise. Recently, very strong results have been obtained by Schramm and Steif [34] and Garban, Pete and Schramm [21] in the discrete case. In [34] it was proven that the noise sensitivity exponents for bond percolation on the square lattice, and for site percolation on the triangular lattice, are positive. The latter was improved in [21] to show that the noise sensitivity exponent for the triangular lattice equals 3/4. Such a precise result was possible to obtain due to the very precise information available on the decay rate of arms events. It would be interesting to determine the precise value of the noise sensitivity exponent in the continuum setting.
One possible application of a solution to Problem 1 would be to Dynamical Continuum Percolation. To define this model, consider a set η chosen according to a Poisson point process of intensity λ c in three dimensions (two space and one time), and suppose points of η disappear at rate one. By Corollary 3.2, at any given time there is (almost surely) no infinite component in D(η); we therefore say that t is an exceptional time if there is an infinite component in D(η) at time t.
The following conjecture was proved for site percolation on the triangular lattice in [34], and for bond percolation on Z 2 in [21]. Conjecture 9.4. There exist exceptional times in Dynamical Continuum Percolation at criticality, almost surely.
A related problem was studied by Benjamini and Schramm [8]. Alternatively, one might first choose the points of η according to a Poisson point process of intensity λ c , and then allow each to perform an independent Brownian motion (see also [16]); an interesting first step would be to prove a result corresponding to Theorem 1.1 for this model. work was continued during a visit by D. Ahlberg to IMPA, whom he thanks for their support and hospitality on several occasions. Finally, we would like to thank the two anonymous referees for their very careful and thorough reading of the paper.