Yitong Yin Proof.We let B=f0,1d\A be the complement of A in the d-dimensional cube. Note that Bl<2d-k.According to our definition of the distribution of r,x is in fact a random (d-r)-dimensional subcube in {0,1]d,and f(,A)=0 only if the cube specified by r 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 2Ef0,14 whose first k bits are all ones.Therefore, Pr[f(,A)=0]<Pr['s first k:bits are all ones] =n-w(1) We then prove that for all s x 26 partitions F of Yy,the probability Pr[3FE F(),f(x,F)={1】and Pr日F∈F(y),f(x,F)={0}]are both very small. For any F∈F(y),we have y∈F,thus3F∈F(y),f(x,F)={1}implies that f(,y)=1,therefore for an arbitrary s x 26 partition F of y, F∈F(,fz,F)）={≤Pf,= ≤Pr日z∈y,x matches z 工，y ≤n.2-r =o(1) To bound the probability PrFF(y),f(x,F)={0}],we observe that each sx 25 partition F is just a union of s many partitions of Y,each of which is with cardinality at most 2,therefore,by union bounds,it holds that gF∈F(U,fz,F)=o1≤sfz,P()=o. (1) for some partition P of y where P<25.It is then sufficient to show that for arbitrary such partition P,the probability Pr[f(,P(y))={0}]is very small. We choose a threshold k =logn,and separate the case that P(y)< (()2")and the case that ()>(()2).According to Lemma 2,for any partition Pof Y with≤2，the probability that(gl≤(1-2行2)= (/2nis at most n() We let Ay=UP(y)=UveP().Note that Ay (0,1)4,and f(,P(y))= (0}implies that f(,A)=0.For such P(y)that P(y)>(()2),by the Pigeonhole Principle,it holds that Au>(1-2-)2d.Due to Lemma 3, f(,Ay)=0 with prohibitively small probability.Putting these together,it holds8 Yitong Yin Proof. We let B = {0, 1} d \A be the complement of A in the d-dimensional cube. Note that |B| < 2 d−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 = n −ω(1) . ut We then prove that for all s × 2 b 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 very 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 × 2 b 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 = o(1). To bound the probability Pr[∃F ∈ F(y), f(x, F) = {0}], we observe that each s × 2 b 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) for some partition P of Y where |P| ≤ 2 b . It is then sufficient to show that for arbitrary such partition P, the probability Pr[f(x,P(y)) = {0}] is very small. We choose a threshold k = 1 2 log n, and separate the case that |P(y)| ≤ ￾ (1−2 −k )2d n
and the case that |P(y)| > ￾ (1−2 −k )2d n
. According to Lemma 2, for any partition P of Y with |P| ≤ 2 b , the probability that |P(y)| ≤ ￾ (1−2 −k )2d n
= ￾ 2 d n
/2 n Ω(1) is at most n −ω(1) . We let Ay = S P(y) = S y0∈P(y) y 0 . Note that Ay ⊆ {0, 1} d , and f(x,P(y)) = {0} implies that f(x, Ay) = 0. For such P(y) that |P(y)| > ￾ (1−2 −k )2d n
, by the Pigeonhole Principle, it holds that |Ay| ≥ (1 − 2 −k )2d . Due to Lemma 3, f(x, Ay) = 0 with prohibitively small probability. Putting these together, it holds