Yitong Yin Partial match:=(01,)4,Y=((0)),and f(,y)e11}such that for every z∈X and y∈Y,f(x,y)=1 if and only if there exists z∈y having either xi =zi or i=*for every i. Polynomial evaluation: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(r). A classic computational model for static data structures is the cell-probe model [11].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 an all-powerful algorithm tries to compute f(r,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 nondeterministic cell-probes and the tradeoff between the number of probes needed and with space.We speculate that it is an important problem because:(1)in considering the complexity of data structures,nondeterminism is a very natural extension to the cell-probe model;(2)instead of adaptive computations,nondeterministic cell-probes capture the question of verification,which is a natural and important aspect of data structures. Although nondeterministic cell-probe complexity is an important problem, there are few general tools and techniques for studying it,especially for the case of static data structures.In fact,because of the great generality of the cell- probe model,even for deterministic cell-probe complexity,super-constant lower bounds for static data structures are rare.Nondeterminism grants the cell-probe model extra power and makes non-trivial lower bounds even rarer.For many standard examples of data structure problems,such as membership query,it is easy to construct a data structure that has standard space usage and constant 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 super-constant.More importantly, it calls for a general technique to prove lower bounds on the nondeterministic cell-probe complexity of static data structures. 1.1 Our contribution In this paper,we initiate the study of nondeterministic cell-probe complexity for static data structures.As a first step,we characterize the power of a single- cell nondeterministic probe.Although at first glance this may seem like a very restricted case,by applying a trivial parameter reduction,we show that the case of a single-cell probe is actually a canonical case for all nondeterministic cell- probe mechanisms,and is thus sufficient to prove super-constant lower bounds for general nondeterministic cell-probe mechanisms.2 Yitong Yin Partial match: 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: 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 [11]. 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 nondeterministic cell-probes and the tradeoff between the number of probes needed and with space. We speculate that it is an important problem because: (1) in considering the complexity of data structures, nondeterminism is a very natural extension to the cell-probe model; (2) instead of adaptive computations, nondeterministic cell-probes capture the question of verification, which is a natural and important aspect of data structures. Although nondeterministic cell-probe complexity is an important problem, there are few general tools and techniques for studying it, especially for the case of static data structures. In fact, because of the great generality of the cell￾probe model, even for deterministic cell-probe complexity, super-constant lower bounds for static data structures are rare. Nondeterminism grants the cell-probe model extra power and makes non-trivial lower bounds even rarer. For many standard examples of data structure problems, such as membership query, it is easy to construct a data structure that has standard space usage and constant 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 super-constant. More importantly, it calls for a general technique to prove lower bounds on the nondeterministic cell-probe complexity of static data structures. 1.1 Our contribution In this paper, we initiate the study of nondeterministic cell-probe complexity for static data structures. As a first step, we characterize the power of a single￾cell nondeterministic probe. Although at first glance this may seem like a very restricted case, by applying a trivial parameter reduction, we show that the case of a single-cell probe is actually a canonical case for all nondeterministic cell￾probe mechanisms, and is thus sufficient to prove super-constant lower bounds for general nondeterministic cell-probe mechanisms