Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity The partial match problem is defined as follow:The domain is a Hamming cube {0,1d,where d=w(logn)nn(1),and each data instance y is a set of n points from the domain,i.e.Y().The set of queries is=1 Given a data instancey∈(o,1 and a query∈{0，l,*}4,fz,g)=1if and only if there is a zEy such that z matches x except for the bits assigned with “*” Theorem 2.There is no (s,b,1)-CPP for the partial match problem,if s= Poly(n)and b=no(1). Proof.We denote the problem as f.From the characterization of(s,b,1)-CPP given in Theorem 1,it is sufficient to show that for any s x 2 partition F of y, there exist x∈X and y∈Y such that for all F∈F(y),lf(z,F)l=2.We prove this with the probabilistic method.With some distribution of x and y,we show that for any s x 25 partition F of Y,Pr[VF EF(y),If(,F)=2]>0. For the rest of the proof,we assume that y is uniformly selected from Y,and x is generated by uniformly choosing r 2logn bits and fixing each of them uniformly and independently at random with 0 or 1,and setting the other bits to“*”. We then prove two supporting lemmas.Recall that for a partition P of Y, P(y)denotes the set F∈P that y∈F. Lemma 2.For any partition P ofY,if P<2b,where b=no(1),then ≤n-w(1) Proof.We let P={F1,F2,...,Fk}where k 25,and let pi =Fil/Yl.Because p is a partition of Y,we know that ipi=1.We define a random variable 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 26 different P(y),by union bound, P[P≤(（）/网]sPrz=AemS2amj =2-n0(a) =nw(1) 0 For simplicity,we generalize the notation of f to arbitrary point set A {0,1)4,where f(,A)is conventionally defined to indicate whether there is a z∈A that matches z Lemma 3.For any AC(0,1)d,if Al>(1-2-)2d for k=logn,then Pr[f(x,A)=0≤n-w().Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity 7 The partial match problem is defined as follow: The domain is a Hamming cube {0, 1} d , where d = ω(log n) ∩ n o(1), and each data instance y is a set of n points from the domain, i.e. Y = ￾ {0,1} d n
. The set of queries is X = {0, 1, ∗}d . Given a data instance y ∈ ￾ {0,1} d n
and a query x ∈ {0, 1, ∗}d , f(x, y) = 1 if and only if there is a z ∈ y such that z matches x except for the bits assigned with “∗”. Theorem 2. There is no (s, b, 1)-CPP for the partial match problem, if s = Poly(n) and b = n o(1) . Proof. We denote the problem as f. From the characterization of (s, b, 1)-CPP given in Theorem 1, it is sufficient to show that for any s × 2 b partition F of Y , there exist x ∈ X and y ∈ Y such that for all F ∈ F(y), |f(x, F)| = 2. We prove this with the probabilistic method. With some distribution of x and y, we show that for any s × 2 b partition F of Y , Pr[∀F ∈ F(y), |f(x, F)| = 2] > 0. For the rest of the proof, we assume that y is uniformly selected from Y , and x is generated by uniformly choosing r = 2 log n bits and fixing each of them uniformly and independently at random with 0 or 1, and setting the other bits to “∗”. We then prove two supporting lemmas. Recall that for a partition P of Y , P(y) denotes the set F ∈ P that y ∈ F. Lemma 2. For any partition P of Y , if |P| ≤ 2 b , where b = n o(1), then Pr y  |P(y)| ≤  2 d n . 2 n Ω(1)  ≤ n −ω(1) . Proof. We let P = {F1, F2, . . . , Fk} where k ≤ 2 b , and let pi = |Fi |/|Y |. Because P is a partition of Y , we know that P i pi = 1. We define a random variable 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)| ≤  2 d n . 2 n Ω(1)  ≤ 2 b · Pr h Z = pi where pi ≤ 2 −n Ω(1) i = 2b−n Ω(1) = n −ω(1) . ut For simplicity, we generalize the notation of f to 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 3. For any A ⊆ {0, 1} d , if |A| > (1 − 2 −k )2d for k = 1 2 log n, then Pr x [f(x, A) = 0] ≤ n −ω(1)