Cell-Probe Proofs ·1:3 Although nondeterministic cell-probe complexity is an important problem,the optimal nondeterministic bounds for static data structure problems are still un- known.For many naturally defined data structure problems,nondeterminism trivializes the problem in the sense that a constant number of nondeterministic cell-probes are sufficient to answer the queries.For the problems that remain nontrivial after allowing nondeterminism,no lower bounds are known for the nondeterministic cell-probe complexity. It is thus worth asking whether there exists any data structure problem such that in data structures with feasible sizes(polynomial in the size of data set),the nondeterministic cell-probe complexity is relatively high.More impor- tantly,it calls for a general technique to prove lower bounds on the nondeter- ministic cell-probe complexity of static data structures. 1.1 Our Contribution In this article.we initiate the study of nondeterministic cell-probe complexity for static data structures. We introduce cell-probe proofs,a proof system in the cell-probe model.This notion of proof corresponds to considering verification instead of computation in the cell-probe model.Unlike the fully adaptive computation in the tradi- tional cell-probe model,the formulation of cell-probe proofs shows a combinato- rial simplicity.We introduce a combinatorial structure that fully characterizes which problems have cell-probe proofs with specified parameters. With these novel tools,we show the following lower bounds on nondetermin- istic cell-probe complexity. -There exists a data structure problem with high nondeterministic cell-probe complexity.This result can be seen as a nondeterministic parallel to the existential lower bound for deterministic cell-probe complexity in Miltersen [1999],which is proved by counting.As mentioned in Miltersen [2008],the nondeterministic lower bound cannot be easily proved by the similar count- ing argument -For the exact nearest neighbor search(NNS)problem or the partial match problem in high dimensional Hamming space,for any data structure with Poly(n)cells,each of which contains O(nc)bits where C 1,the nonde- terministic cell-probe complexity is at least (log(d/logn)),where d is the dimension and n is the number of points in the data set.The highest known deterministic cell-probe lower bound for the problems for polynomial space is Q(d/logn)(see Barkol and Rabani [2002]and Patrascu [2008]).These lower bounds are proved by communication complexity techniques. -For the polynomial evaluation problem of d-degree polynomial over a fi- nite field of size 2 where d is high,for any data structure with s cells, each of which contains 6 bits,the nondeterministic cell-probe complex- ity is at least min 1).) This bound is nearly equal to the ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.Cell-Probe Proofs · 1: 3 Although nondeterministic cell-probe complexity is an important problem, the optimal nondeterministic bounds for static data structure problems are still un￾known. For many naturally defined data structure problems, nondeterminism trivializes the problem in the sense that a constant number of nondeterministic cell-probes are sufficient to answer the queries. For the problems that remain nontrivial after allowing nondeterminism, no lower bounds are known for the nondeterministic cell-probe complexity. It is thus worth asking whether there exists any data structure problem such that in data structures with feasible sizes (polynomial in the size of data set), the nondeterministic cell-probe complexity is relatively high. More impor￾tantly, it calls for a general technique to prove lower bounds on the nondeter￾ministic cell-probe complexity of static data structures. 1.1 Our Contribution In this article, we initiate the study of nondeterministic cell-probe complexity for static data structures. We introduce cell-probe proofs, a proof system in the cell-probe model. This notion of proof corresponds to considering verification instead of computation in the cell-probe model. Unlike the fully adaptive computation in the tradi￾tional cell-probe model, the formulation of cell-probe proofs shows a combinato￾rial simplicity. We introduce a combinatorial structure that fully characterizes which problems have cell-probe proofs with specified parameters. With these novel tools, we show the following lower bounds on nondetermin￾istic cell-probe complexity. —There exists a data structure problem with high nondeterministic cell-probe complexity. This result can be seen as a nondeterministic parallel to the existential lower bound for deterministic cell-probe complexity in Miltersen [1999], which is proved by counting. As mentioned in Miltersen [2008], the nondeterministic lower bound cannot be easily proved by the similar count￾ing argument. —For the exact nearest neighbor search (NNS) problem or the partial match problem in high dimensional Hamming space, for any data structure with Poly(n) cells, each of which contains O(nC) bits where C < 1, the nonde￾terministic cell-probe complexity is at least log d/ log n , where d is the dimension and n is the number of points in the data set. The highest known deterministic cell-probe lower bound for the problems for polynomial space is (d/ logn) (see Barkol and Rabani [2002] and Patras ˘ ¸cu [2008]). These lower bounds are proved by communication complexity techniques. —For the polynomial evaluation problem of d-degree polynomial over a fi- nite field of size 2k where d is high, for any data structure with s cells, each of which contains b bits, the nondeterministic cell-probe complex￾ity is at least min  k b (d − 1), k−log(d−1) log s  . This bound is nearly equal to the ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.