1:4.Y.Yin (mind+1deterministic lower bound [Miltersen 9nwhich it is assumed that 6 =k 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 nontrivial 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.[1998]. Fredman and Saks [1989],introduce the chronogram method.This power- ful technique is specialized for proving the query/update tradeoff for dynamic data structures,especially for the problems that are hard only in the dynamic case.It is worth noting that the chronogram method can prove nondetermin- istic lower bounds for certain dynamic data structure problems.This is for- mally addressed by Husfeldt and Rauhe in [1998],and recently by Patrascu and Demaine [2006].However,as pointed in Husfeldt and Rauhe [1998],this is only a byproduct of the nondeterministic nature of chronogram method,and can only yield amortized query/update tradeoffs for dynamic data structure problems with a certain property.Due to the unique structure of the chrono- gram method,this technique cannot be utilized to prove lower bounds for static data structures. 2.CELL-PROBE PROOFS A static data structure problem is represented as a boolean function f:XxY> (0,1).For the purposes of proving lower bounds,it is sufficient to consider only the decision problems.We refer to each y e y as data and each x e X as a query.For each pair ofx and y,f(x,y)specifies the result of the query x to the data structure that represents the data y. In the cell-probe model(c.f.,Fredman and Saks [1989];Yao [1981]),the data instance y is preprocessed and stored in cells,and for each query x,the value of f(x,y)is decided by adaptive probes to the cells.Formally,a cell-probe scheme consists of a table structure and a query algorithm.The table structure T: YxI>(0,1)5 specifies a table T:I>(0,1)5 for each data instance y,which maps indices of cells to their contents.Given a query x,the query algorithm makes a sequence of probes i,i2,...to the cells,where is depends on x,and all previous cell probes (i,T,(i1),(i2,T,(i2),...,(i1,T(i-1)).The value of f(x,y)is decided at last based on the collected information. In this work,we focus on nondeterministic cell-probes.Given a query x to a data instance y,a set oft cells i1,i2,...,i are probed nondeterministically,such that the value of f(x,y)can be uniquely decided on the query input x and the probed information. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.1: 4 · Y. Yin  min  d + 1, k−log d log s  deterministic lower bound [Miltersen 1995], in which it is assumed that b = k. 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 nontrivial 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. [1998]. Fredman and Saks [1989], introduce the chronogram method. This power￾ful technique is specialized for proving the query/update tradeoff for dynamic data structures, especially for the problems that are hard only in the dynamic case. It is worth noting that the chronogram method can prove nondetermin￾istic lower bounds for certain dynamic data structure problems. This is for￾mally addressed by Husfeldt and Rauhe in [1998], and recently by Patras ˘ ¸cu and Demaine [2006]. However, as pointed in Husfeldt and Rauhe [1998], this is only a byproduct of the nondeterministic nature of chronogram method, and can only yield amortized query/update tradeoffs for dynamic data structure problems with a certain property. Due to the unique structure of the chrono￾gram method, this technique cannot be utilized to prove lower bounds for static data structures. 2. CELL-PROBE PROOFS A static data structure problem is represented as a boolean function f : X ×Y → {0, 1}. For the purposes of proving lower bounds, it is sufficient to consider only the decision problems. We refer to each y ∈ Y as data and each x ∈ X as a query. For each pair of x and y, f(x, y) specifies the result of the query x to the data structure that represents the data y. In the cell-probe model (c.f., Fredman and Saks [1989]; Yao [1981]), the data instance y is preprocessed and stored in cells, and for each query x, the value of f(x, y) is decided by adaptive probes to the cells. Formally, a cell-probe scheme consists of a table structure and a query algorithm. The table structure T : Y × I → {0, 1}b specifies a table Ty : I → {0, 1}b for each data instance y, which maps indices of cells to their contents. Given a query x, the query algorithm makes a sequence of probes i1,i2,... to the cells, where ik depends on x, and all previous cell probes  i1, Ty(i1)  ,  i2, Ty(i2)  ,..., ik−1, Ty(ik−1)  . The value of f(x, y) is decided at last based on the collected information. In this work, we focus on nondeterministic cell-probes. Given a query x to a data instance y, a set of t cells i1,i2,...,it are probed nondeterministically, such that the value of f(x, y) can be uniquely decided on the query input x and the probed information. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010