Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity

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 computations in the cell-probe model. We present a combinatorial characterization 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 nondeterministic 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.