Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity 3 We introduce cell-probe proofs.a proof system in the cell-probe model.This notion of proofs corresponds to considering verifications instead of computations in the cell-probe model.Unlike the fully adaptive computations in the traditional cell-probe model,the formulation of cell-probe proofs shows a combinatorial simplicity.We introduce a combinatorial structure that fully characterizes which problems have single-cell proofs,and general cell-probe proofs are reduced to this case. With these novel tools,we show following lower bounds on nondeterministic cell-probe complexity: We show that there exist static data structure problems with super-constant nondeterministic cell-probe complexity.In particular,we show that for the exact nearest neighbor search(NNS)problem or 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()bits,such that the nonde- terministic 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 for a static data structure,the single-cell nondeterministic probes are sufficient to answer queries,then ei- ther the size of the single cell is close to the size of the whole polynomial,or the total size of the data structure is close to that of the naive data structure that stores results for all possible queries. 1.2 Related work To the best of our knowledge,there is no general technique for proving lower bounds for nondeterministic cell-probe complexity of static data structures.Nor do there exist any non-trivial lower bounds for this question.Previous work on static data structures in the cell-probe model have focused on the complexity of adaptive cell-probes.The most important tool for proving such lower bounds is asymmetric communication complexity as introduced by Miltersen et al.in [10]. In [6],Fredman and Saks introduce the chronogram method.This powerful technique is specialized for proving the query /update trade-off for dynamic data structures,especially for the problems which are hard only in the dynamic case. It is worth noting that the chronogram method can prove nondeterministic lower bounds for certain dynamic data structure problems.This is formally addressed by Husfeldt and Rauhe in [7],and recently by Demaine and Patrascu in [5]. However,as pointed in [7],this is only a by-product of the nondeterministic nature of chronogram method and can only yield amortized query/update trade- offs for dynamic data structure problems with a certain property.Because of the unique structure of the chronogram method,this technique can not be utilized to prove lower bounds for static data structures. 2 Cell-probe proofs A static data structure problem or just data structure problem,is rep resented as a boolean function f:Xx Y10,1}.For the purposes of provingCell-Probe Proofs and Nondeterministic Cell-Probe Complexity 3 We introduce cell-probe proofs, a proof system in the cell-probe model. This notion of proofs corresponds to considering verifications instead of computations in the cell-probe model. Unlike the fully adaptive computations in the traditional cell-probe model, the formulation of cell-probe proofs shows a combinatorial simplicity. We introduce a combinatorial structure that fully characterizes which problems have single-cell proofs, and general cell-probe proofs are reduced to this case. With these novel tools, we show following lower bounds on nondeterministic cell-probe complexity: – We show that there exist static data structure problems with super-constant nondeterministic cell-probe complexity. In particular, we show that for the exact nearest neighbor search (NNS) problem or 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 nonde￾terministic 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 for a static data structure, the single-cell nondeterministic probes are sufficient to answer queries, then ei￾ther the size of the single cell is close to the size of the whole polynomial, or the total size of the data structure is close to that of the naive data structure that stores results for all possible queries. 1.2 Related work To the best of our knowledge, there is no general technique for proving lower bounds for nondeterministic cell-probe complexity of static data structures. Nor do there exist any non-trivial lower bounds for this question. Previous work on static data structures in the cell-probe model have focused on the complexity of adaptive cell-probes. The most important tool for proving such lower bounds is asymmetric communication complexity as introduced by Miltersen et al. in [10]. In [6], Fredman and Saks introduce the chronogram method. This powerful technique is specialized for proving the query/update trade-off for dynamic data structures, especially for the problems which are hard only in the dynamic case. It is worth noting that the chronogram method can prove nondeterministic lower bounds for certain dynamic data structure problems. This is formally addressed by Husfeldt and Rauhe in [7], and recently by Demaine and P˘atra¸scu in [5]. However, as pointed in [7], this is only a by-product of the nondeterministic nature of chronogram method and can only yield amortized query/update trade￾offs for dynamic data structure problems with a certain property. Because of the unique structure of the chronogram method, this technique can not be utilized to prove lower bounds for static data structures. 2 Cell-probe proofs A static data structure problem or just data structure problem, is rep￾resented as a boolean function f : X × Y → {0, 1}. For the purposes of proving