Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity Yitong Yin* Department of Computer Science,Yale University yitong.yin@yale.edu. Abstract.We study the nondeterministic cell-probe complexity of static data structures.We introduce cell-probe proofs (CPP),a proof system for the cell-probe model,which describes verifications instead of compu- tations in the cell-probe model.We present a combinatorial characteri- zation of CPP.With this novel tool,we prove the following lower bounds for the nondeterministic cell-probe complexity of static data structures: We show that there exist data structure problems which have super- constant nondeterministic cell-probe complexity.In particular,we show that for the exact nearest neighbor search(NNS)problem or the partial match problem in high dimensional Hamming space,there does not exist a static data structure with Poly(n)cells,each of which contains n(1)bits,such that the nondeterministic cell-probe complexity is O(1),where n is the number of points in the data set for the NNS or partial match problem. For the polynomial evaluation problem,if single-cell nondeterminis- tic probes are sufficient,then either the size of a single cell is close to the size of the whole polynomial,or the total size of the data structure is close to that of a naive data structure that stores results for all possible queries. 1 Introduction We study the problem of nondeterministic cell-probe complexity of static data structures. Given a set Y of data instances,and a set X of possible queries,a data structure problem can be abstractly defined as a function f mapping each pair consisting of a query r E X and a data instance y E Y to an answer.One of the most well-studied examples of data structure problems is the "membership query":X=[m]is a data universe,Y=(m),and f(,y)=1 if ey and f(,y)=0 if otherwise. There are some other important examples of data structure problems: Exact nearest neighbor search (NNS):given a metric space U,let X =U and Y =()and for every zEX and yEy,f(z,y)is defined as the closest point to x in y according to the metric. Supported by a Kempner Foundation Fellowship and NSF grant CNS-0435201.Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity Yitong Yin? Department of Computer Science, Yale University yitong.yin@yale.edu. Abstract. We study the nondeterministic cell-probe complexity of static data structures. We introduce cell-probe proofs (CPP), a proof system for the cell-probe model, which describes verifications instead of compu￾tations in the cell-probe model. We present a combinatorial characteri￾zation of CPP. With this novel tool, we prove the following lower bounds for the nondeterministic cell-probe complexity of static data structures: – We show that there exist data structure problems which have super￾constant nondeterministic cell-probe complexity. In particular, we show that for the exact nearest neighbor search (NNS) problem or the partial match problem in high dimensional Hamming space, there does not exist a static data structure with Poly(n) cells, each of which contains n o(1) bits, such that the nondeterministic cell-probe complexity is O(1), where n is the number of points in the data set for the NNS or partial match problem. – For the polynomial evaluation problem, if single-cell nondeterminis￾tic probes are sufficient, then either the size of a single cell is close to the size of the whole polynomial, or the total size of the data structure is close to that of a naive data structure that stores results for all possible queries. 1 Introduction We study the problem of nondeterministic cell-probe complexity of static data structures. Given a set Y of data instances, and a set X of possible queries, a data structure problem can be abstractly defined as a function f mapping each pair consisting of a query x ∈ X and a data instance y ∈ Y to an answer. One of the most well-studied examples of data structure problems is the “membership query”: X = [m] is a data universe, Y = ￾ [m] n
, and f(x, y) = 1 if x ∈ y and f(x, y) = 0 if otherwise. There are some other important examples of data structure problems: Exact nearest neighbor search (NNS): given a metric space U, let X = U and Y = ￾U n
, and for every x ∈ X and y ∈ Y , f(x, y) is defined as the closest point to x in y according to the metric. ? Supported by a Kempner Foundation Fellowship and NSF grant CNS-0435201