Cell-Probe Proofs.1:11 Z=IP(y)/IYI.Since y is picked uniformly at random from Y,it holds that Z= Pi with probability pi.Since there are at most 25 different P(y),by union bound, 9[ro:(-】sn[g=a管] -1 21-224 ) 2驰(1-2-)24” ≤ 2dn ≤exp(bn2-n2-k). ▣ For simplicity,we generalize the notation of f to an arbitrary point set A (0,1)4,where f(x,A)is conventionally defined to indicate whether there isaz∈A that matchesx LEMMA 5.3.For any A C (0,1)d,if Al>(1-2-)2d for some k log n, then ,A=01≤()》 PROOF.We let B=(0,1)\A be the complement of A in the d-dimensional cube.Note that Bl<2d-.According to our definition of the distribution of x. x is in fact a random (d-r)-dimensional subcube in (0,1)4,and f(x,A)=0 only if the cube specified by x is contained in B.This chance is maximized when B itself is a cube.Thus,without loss of generality,we can assume that B is the set ofz (0,1]4 whose first k bits are all ones.Therefore, (d-k Pr[fx,A)=o]≤Pr[x's first k bits are all ones]≤ r-k ▣ We then prove that for all s x 25 partitions F of Y,the probability PrFF(y),f(x,F)=(1]]and Pr[3FF(y),f(x,F)=(0]]are both small. For any F∈Fy,we have y∈F,thus 3F∈Fy),f(x,F)={l}implies that f(x,y)=1,therefore for an arbitrary s x 25 partition F of y, g目FeF,fxD=≤P[fx,)=l刂 ≤[ey,matches z] ≤n.2- 1 2 To bound the probability Pr FF(y),f(x,F)=(0)],we observe that each s x 25 partition F is just a union of s many partitions of y,each of which is with cardinality at most 25,therefore,by union bounds,it holds that Pr目F∈Fy),fx,F)={O]≤s·Pr[fx,Py)={O] (1) X.V ℃1 ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.Cell-Probe Proofs · 1: 11 Z = |P(y)|/|Y|. Since y is picked uniformly at random from Y, it holds that Z = pi with probability pi. Since there are at most 2b different P(y), by union bound, Pr y  P(y) ≤  1 − 2−k 2d n  ≤ 2b · Pr  Z = pi where pi ≤ (1−2−k )2d n 2d n  ≤ 2b (1−2−k )2d n 2d n ≤ 2b 1 − 2−k 2dn 2dn ≤ exp b ln 2 − n2−k . For simplicity, we generalize the notation of f to an arbitrary point set A ⊆ {0, 1}d, where f(x, A) is conventionally defined to indicate whether there is a z ∈ A that matches x LEMMA 5.3. For any A ⊆ {0, 1}d, if |A| > 1 − 2−k 2d for some k < log n, then Pr x [ f(x, A) = 0] ≤  r d k . PROOF. We let B = {0, 1}d \ A be the complement of A in the d-dimensional cube. Note that |B| < 2d−k. According to our definition of the distribution of x, x is in fact a random (d−r)-dimensional subcube in {0, 1}d, and f(x, A) = 0 only if the cube specified by x is contained in B. This chance is maximized when B itself is a cube. Thus, without loss of generality, we can assume that B is the set of z ∈ {0, 1} d whose first k bits are all ones. Therefore, Pr x [ f(x, A) = 0] ≤ Pr x [x’s first k bits are all ones] ≤ d−k r−k d r ≤  r d k . We then prove that for all s × 2b partitions F of Y, the probability Pr[∃F ∈ F(y), f(x, F) = {1}] and Pr[∃F ∈ F(y), f(x, F) = {0}] are both small. For any F ∈ F(y), we have y ∈ F, thus ∃F ∈ F(y), f(x, F) = {1} implies that f(x, y) = 1, therefore for an arbitrary s × 2b partition F of Y, Pr x,y  ∃F ∈ F(y), f(x, F) = {1}  ≤ Pr x,y  f(x, y)=1 ≤ Pr x,y  ∃z ∈ y, x matches z  ≤ n · 2−r = 1 2 . To bound the probability Pr  ∃F ∈ F(y), f(x, F) = {0}  , we observe that each s × 2b partition F is just a union of s many partitions of Y, each of which is with cardinality at most 2b , therefore, by union bounds, it holds that Pr x,y  ∃F ∈ F(y), f(x, F) = {0}  ≤ s · Pr x,y  f x,P(y) = {0}  (1) ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.