Cell-Probe Proofs ·1:13 COROLLARY 5.4.There does not exist a (s,b,1)-CPP for the nearest neigh- bor search problem with n points in d-dimensional Hamming space where d=o(logn)nnod ifs <(d/2logn)alogn and b <nl-a for some constant 0<a 1. Due to Lemma 2.1,the following lower bound on the nondeterministic cell- probe complexity holds. COROLLARY 5.5.There does not exist a (s,b,t)-CPP for the nearest neighbor search problem or the partial match problem with n points in d-dimensional Hamming space where d=oflogn)nno)if s=Poly(n),b nl-a for some constant a 0 and t=o (log(d/logn)). 6.POLYNOMIAL EVALUATION Let 2k be a finite field.Let y 2d be the set of all polynomials of degree s(d-1)over the finite field 2.Throughout this section,we assume that d≤2. Let X =22k be the set of all pairs of elements of the finite field 2.A decision version of the polynomial evaluation problem f is defined as follows:for every query (x,z)EX and every data instancegeY,f ((x,z),g)=1 if g(x)=z and f((x,z),g)=0 otherwise.A polynomialg is preprocessed and stored as a data structure,so that for each query (x,z),the data structure answers whether g(x)=2. There are two naive upper bounds for one-cell proofs: (1)a(1,kd,1)-CPP:store the whole polynomial in a single cell,and on each query,one probe reveals the whole polynomial; (2)a (2,k,1)-CPP:each cell corresponds to an input x,and the cell stores the value of g(x),thus on each query (x,z),one probe to the cell corresponding to x answers whether g(x)=z. We are going to prove that the above naive upper bounds are essentially opti- mal for single-probe proofs.We show that for any (s,b,1)-CPP,either b is close to large enough to store a whole polynomial as in case(1),or the total storage size s.b is exactly as large as in case(2). We first prove two lemmas.For any subset P Y,let r(P)= Ix e2 IVgi,g2 e P,gi(x)=g2(x),which represents the number of such as- signments ofx that all polynomials in P yield the same outcome.It is trivial to see that for Pl<1,(P)=2. LEMMA 6.1.If Pl>1,it holds that (P)sd_logIP PROOF.We write r(P)briefly as t.Let x1,x2....,x be such that all polyno- mials in P yield the same outcomes.We arbitrarily pick other x+1,x+2....,xa. For any two different polynomials gi,g2 e P,it can never hold that gi(xi)= g2(xi)for all i=t+1,t+2,...,d,since,if otherwise,gi =g2 by interpolation. Recall that g is a polynomial over the finite field 2,thus for an arbitrary g e P and an arbitrary x,there are at most 2 possible values for g(x).Therefore,due ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.Cell-Probe Proofs · 1: 13 COROLLARY 5.4. There does not exist a (s, b, 1)-CPP for the nearest neigh￾bor search problem with n points in d-dimensional Hamming space where d = ω(logn)∩no(1) if s < (d/2 log n) α log n and b < n1−α for some constant 0 <α< 1. Due to Lemma 2.1, the following lower bound on the nondeterministic cell￾probe complexity holds. COROLLARY 5.5. There does not exist a (s, b,t)-CPP for the nearest neighbor search problem or the partial match problem with n points in d-dimensional Hamming space where d = ω(log n) ∩ no(1) if s = Poly(n), b < n1−α for some constant α > 0 and t = o log(d/ log n) . 6. 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. Let X = 22k be the set of all pairs of elements of the finite field 2k. A decision version of the polynomial evaluation problem f is defined as follows: for every query (x, z) ∈ X and every data instance g ∈ Y, f (x, z), g = 1 if g(x) = z and f (x, z), g = 0 otherwise. A polynomial g is preprocessed and stored as a data structure, so that for each query (x, z), the data structure answers whether g(x) = z. There are two na¨ıve upper bounds for one-cell proofs: (1) a (1, kd, 1)-CPP: store the whole polynomial in a single cell, and on each query, one probe reveals the whole polynomial; (2) a 2k, k, 1 -CPP: each cell corresponds to an input x, and the cell stores the value of g(x), thus on each query (x, z), one probe to the cell corresponding to x answers whether g(x) = z. We are going to prove that the above naive upper bounds are essentially opti￾mal for single-probe proofs. We show that for any (s, b, 1)-CPP, either b is close to large enough to store a whole polynomial as in case (1), or the total storage size s · b is exactly as large as in case (2). We first prove two lemmas. For any subset P ⊆ Y, let τ (P) =  x ∈ 2k | ∀g1, g2 ∈ P, g1(x) = g2(x) , which represents the number of such as￾signments of x that all polynomials in P yield the same outcome. It is trivial to see that for |P| ≤ 1, τ (P)=2k. LEMMA 6.1. If |P| > 1, it holds that τ (P) ≤ d − log |P| k . PROOF. We write τ (P) briefly as τ . Let x1, x2,..., xτ be such that all polyno￾mials in P yield the same outcomes. We arbitrarily pick other xτ+1, xτ+2,..., xd. For any two different polynomials g1, g2 ∈ P, it can never hold that g1(xi) = g2(xi) for all i = τ + 1, τ + 2,..., d, since, if otherwise, g1 ≡ g2 by interpolation. Recall that g is a polynomial over the finite field 2k, thus for an arbitrary g ∈ P and an arbitrary x, there are at most 2k possible values for g(x). Therefore, due ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.