1:12·Y.Yin for some partition P of y where IP<25.It is then sufficient to show that for an arbitrary such partition P,the probability Pr[f(x,P(y))=(0)]is small. We choose a threshold k alogn,and separate the case that (y)(()2)and the case that P(y)>().According to Lemma 5.2,for any partition P of y with IPs 25,the probability that (y)((2)is at most exp(6 In2-n(1-a). We let A =UP(y)=Uye.Note that A (0,1)d and f(,P(y))=(0) imply that f(x,A)=0.For such P(y)that y)>((2)),it holds by the Pigeonhole Principle that Al >(1-2-k)2d.Then due to Lemma 5.3, that f(x,A)=0 holds with probability at most ()log".Putting the above arguments together,it holds for any partition P of y with IPls25 that [r,=ol≤p[Pl≤(-2）】] +[re=olp>(-2】 ≤exp(bln2-na-a） +Pg[f(e,UP)=0Upo>1-2-)2] ≤exp(bln2-na-a）+(月)s" Combining with(1),we have that gren在=o刚ss(om6n2--）+(+g9）e） For such s and b that s <(d/2logn)logn and b nl-a,the above probability is o(1).Therefore, g[FeF|f,F=2≥1-g目FeF,fx,)= -Pr[自F∈Fy),fx,F)={O] 1 >2-o10. It follows that for any s x 25 partition F of y with the above setting of s and b, there existx eX andy e Y such that for every FeF(y),it holds that If(x,F)I= 2.By Corollary 3.3,there is no (s,6,1)-CPP for f with such range ofs and b. In Borodin et al.[1999],it is shown that the partial match problem can be reduced to the A-NN problem.Because the reduction only involves mapping be- tween 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. Therefore,the same lower bound holds for A-NN. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.1: 12 · Y. Yin for some partition P of Y where |P| ≤ 2b . It is then sufficient to show that for an arbitrary such partition P, the probability Pr[ f(x,P(y)) = {0}] is small. We choose a threshold k = α 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 5.2, for any partition P of Y with |P| ≤ 2b , the probability that P(y) ≤ (1−2−k )2d n is at most exp b ln 2 − n(1−α) . We let A =  P(y) =  y ∈P(y) y . Note that A ⊆ {0, 1} d and f x,P(y) = {0} imply that f(x, A) = 0. For such P(y) that P(y) > (1−2−k )2d n , it holds by the Pigeonhole Principle that |A| ≥ 1 − 2−k 2d. Then due to Lemma 5.3, that f(x, A) = 0 holds with probability at most ( r d) α log n. Putting the above arguments together, it holds for any partition P of Y with |P| ≤ 2b 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  ≤ exp bln 2 − n(1−α)  + Prx  f  x, P(y)  = 0 P(y) > 1 − 2−k 2d  ≤ exp bln 2 − n(1−α)  +  r d α log n . Combining with (1), we have that Pr x,y  ∃F ∈ F(y), f(x, F) = {0}  ≤ s ·  exp bln 2 − n(1−α)  + 1 + log n d α log n  . For such s and b that s < (d/2 log n) α log n and b < n1−α, the above probability is o(1). Therefore, 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 2 − o(1) . It follows that for any s × 2b partition F of Y with the above setting of s and b, there exist x ∈ X and y ∈ Y such that for every F ∈ F(y), it holds that | f(x, F)| = 2. By Corollary 3.3, there is no (s, b, 1)-CPP for f with such range of s and b. In Borodin et al. [1999], it is shown that the partial match problem can be reduced to the λ-NN problem. Because the reduction only involves mapping be￾tween 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. Therefore, the same lower bound holds for λ-NN. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.