Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity for an arbitrary partition P of y with P<26 that Ue,Po=I≤g[pol≤(-Tr)] +ero-opo>(-】 ≤naa+Prfz,A,）=0l4,l>(1-2-*)2 ≤nw(1) Combining with (1),we have that gF∈F,fe,F)={01≤sn-=oL). Therefore,for an arbitrary sx 26 partition F of y,it holds that gFeF),lf(z,F1=2≥1-PrF∈F(,f,F)={1H I.y -Pr日F∈F(y),f(x,F)={0] z.y ≥1-o(1) It follows that for any s x 26 partition F of y,where s=Poly(n)and b=n(1) there exist z∈X and y∈Y such that for every F∈F(y),it holds that If(,F)=2.By Theorem 1,there is no (s,b,1)-CPP for f with the above range of s and b. ▣ In [3],it is shown that the partial match problem can be reduced to the A-NN problem.Because the reduction only involves mapping between instances of problems,the existence of an (s,b,1)-CPP for A-NN implies the existence of a CPP for partial match with essentially the same parameters.The following corollary is implied. Corollary 1.There does not erist a (Poly(n),n(1),1)-CPP for the nearest neighbor search problem with n points in d-dimensional Hamming space where d =w(logn)nno(1). Due to Lemma 1,the following super-constant lower bound on the nondeter- ministic cell-probe complexity holds. Corollary 2.There does not erist a (Poly(n),n01),O(1))-CPP for the near- est neighbor search problem or the partial match problem with n points in d- dimensional Hamming space where d=w(logn)n(1). 5 Polynomial evaluation Let 2k be a finite field.Let Y=2kd be the set of all polynomials of degree <(d-1)over the finite field 2k.Throughout this section,we assume that d≤2k.Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity 9 for an arbitrary partition P of Y with |P| ≤ 2 b that Pr x,y [f(x,P(y)) = {0}] ≤ Pr y  |P(y)| ≤  (1 − 2 −k )2d n  + Pr x,y  f(x,P(y)) = {0}     |P(y)| >  (1 − 2 −k )2d n  ≤ n −ω(1) + Pr x h f(x, Ay) = 0    |Ay| > (1 − 2 −k )2d i ≤ n −ω(1) . Combining with (1), we have that Pr x,y [∃F ∈ F(y), f(x, F) = {0}] ≤ s · n −ω(1) = o(1). Therefore, for an arbitrary s × 2 b partition F of Y , it holds that Pr x,y [∀F ∈ F(y), |f(x, F)| = 2] ≥ 1 − Pr x,y [∃F ∈ F(y), f(x, F) = {1}] − Pr x,y [∃F ∈ F(y), f(x, F) = {0}] ≥ 1 − o(1). It follows that for any s × 2 b partition F of Y , where s = Poly(n) and b = n o(1) , there exist x ∈ X and y ∈ Y such that for every F ∈ F(y), it holds that |f(x, F)| = 2. By Theorem 1, there is no (s, b, 1)-CPP for f with the above range of s and b. ut In [3], it is shown that the partial match problem can be reduced to the λ-NN problem. Because the reduction only involves mapping between instances of problems, the existence of an (s, b, 1)-CPP for λ-NN implies the existence of a CPP for partial match with essentially the same parameters. The following corollary is implied. Corollary 1. There does not exist a (Poly(n), no(1) , 1)-CPP for the nearest neighbor search problem with n points in d-dimensional Hamming space where d = ω(log n) ∩ n o(1) . Due to Lemma 1, the following super-constant lower bound on the nondeter￾ministic cell-probe complexity holds. Corollary 2. There does not exist a (Poly(n), no(1), O(1))-CPP for the near￾est neighbor search problem or the partial match problem with n points in d￾dimensional Hamming space where d = ω(log n) ∩ n o(1) . 5 Polynomial evaluation Let 2k be a finite field. Let Y = 2kd be the set of all polynomials of degree ≤ (d − 1) over the finite field 2k . Throughout this section, we assume that d ≤ 2 k