1:2 .Y.Yin Given a set Y of data instances and a set X of possible queries,a data struc- ture problem can be abstractly defined as a function f mapping each pair con- sisting ofa queryx 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(x,y)=1ifxey and f(x.y)=o if otherwise. There are some other important examples of data structure problems: Exact nearest neighbor search (NNS)[Barkol and Rabani 2002;Borodin et al.1999;Indyk et al.2004]:given a metric space U,let X =U and Y=(U),and for every xX and y Y,f(x,y)is defined as the closest point to x in y according to the metric. Partial match [Borodin et al.1999;Jayram et al.2004;Patrascu 2008]: =(0.1,Y =(10 )and f(x.y)e(0,1)such that for every xx and y e Y,f(x,y)=1 if and only if there exists z ey having either xi=z or xi=*for every i. Polynomial evaluation [Miltersen 1995]:X =2k is a finite field,Y =2kd is the set of all (d-1)-degree polynomials over the finite field 2,and f(x,y) returns the value of y(x). A classic computational model for static data structures is the cell-probe model Yao [1981].For each data instance y,a table of cells is constructed to store y. This table is called a static data structure for some problem f.Upon a query x, an all-powerful algorithm tries to compute f(x,y),based on adaptive random access(probes)to the cells. The cell-probe model is a clean and general model for static data structures, and serves as a great tool for the study of lower bounds.Previous research on static data structures in the cell-probe model has focused on the complexity of adaptive cell-probes.In this work,we focus on the complexity of nondeter- ministic cell-probes and the tradeoff between the number of probes needed and space.We speculate that it is an important problem with following motivations: (1)In considering the complexity of data structures,nondeterminism is a very natural extension to the cell-probe model.Instead of adaptive computa- tions,nondeterministic cell-probes capture the notion of verification,which is a natural and important aspect of data structures. (2)A classic tool for analyzing the cell-probe model is communication complex- ity [Kushilevitz and Nisan 1997;Miltersen et al.1998],for which the com- putations in a data structure are viewed as communications between two adaptive players.This observation makes computations in data structures analyzable by granting the data structure extra power(i.e.,an adaptive table).By the same light,assuming nondeterminism provides us a differ- ent way of proving lower bounds:instead of having a table that can "talk," it assumes a probing algorithm that can "guess". ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.1: 2 · Y. Yin Given a set Y of data instances and a set X of possible queries, a data struc￾ture problem can be abstractly defined as a function f mapping each pair con￾sisting 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) [Barkol and Rabani 2002; Borodin et al. 1999; Indyk et al. 2004]: 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. Partial match [Borodin et al. 1999; Jayram et al. 2004; Patras ˘ ¸cu 2008]: X = {0, 1, ∗}d, Y = {0,1}d n , and f(x, y) ∈ {0, 1} such that for every x ∈ X and y ∈ Y, f(x, y) = 1 if and only if there exists z ∈ y having either xi = zi or xi = ∗ for every i. Polynomial evaluation [Miltersen 1995]: X = 2k is a finite field, Y = 2kd is the set of all (d− 1)-degree polynomials over the finite field 2k, and f(x, y) returns the value of y(x). A classic computational model for static data structures is the cell-probe model Yao [1981]. For each data instance y, a table of cells is constructed to store y. This table is called a static data structure for some problem f. Upon a query x, an all-powerful algorithm tries to compute f(x, y), based on adaptive random access (probes) to the cells. The cell-probe model is a clean and general model for static data structures, and serves as a great tool for the study of lower bounds. Previous research on static data structures in the cell-probe model has focused on the complexity of adaptive cell-probes. In this work, we focus on the complexity of nondeter￾ministic cell-probes and the tradeoff between the number of probes needed and space. We speculate that it is an important problem with following motivations: (1) In considering the complexity of data structures, nondeterminism is a very natural extension to the cell-probe model. Instead of adaptive computa￾tions, nondeterministic cell-probes capture the notion of verification, which is a natural and important aspect of data structures. (2) A classic tool for analyzing the cell-probe model is communication complex￾ity [Kushilevitz and Nisan 1997; Miltersen et al. 1998], for which the com￾putations in a data structure are viewed as communications between two adaptive players. This observation makes computations in data structures analyzable by granting the data structure extra power (i.e., an adaptive table). By the same light, assuming nondeterminism provides us a differ￾ent way of proving lower bounds: instead of having a table that can “talk,” it assumes a probing algorithm that can “guess”. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.