Cell-Probe Proofs YITONG YIN Nanjing University 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 verification instead of computation 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. -There exists a data structure problem with high nondeterministic cell-probe complexity. -For the exact nearest neighbor search(NNS)problem or the partial match problem in high di- mensional Hamming space,for any data structure with Poly(n)cells,each of which contains O(nc)bits where C 1,the nondeterministic cell-probe complexity is at least (log(d/logn)). where d is the dimension and n is the number of points in the data set. -For the polynomial evaluation problem of d-degree polynomial over finite field of size 2k where ds 2,for any data structure with s cells,each of which contains b bits,the nondeterministic cell-probe complexity is at least min ((d-1). 10g8 Categories and Subject Descriptors:E.1 [Datal:Data Structures;F.1.2 [Computation by Abstract Devices]:Modes of Computation General Terms:Theory Additional Key Words and Phrases:Cell-probe model,nondeterminism ACM Reference Format: Yin,Y.2010.Cell-probe proofs.ACM Trans.Comput.Theory,2,1,Article 1(November 2010), 17 pages..D0I-10.1145/1867719.1867720.http/doi.acm.org/10.1145/1867719.1867720. 1.INTRODUCTION We study the problem of the nondeterministic cell-probe complexity of static data structures. This work was supported by the Program for New Century Excellent Talents at University(NCET) and by the National Science Foundation of China under grant 60721002. A preliminary version of this article appeared in the Proceedings of the 35th International Collo. quium on Automata,Languages and Programming,pp.72-83. Author's address:Y.Yin,Nanjing University,Department of Computer Science and Technology,22 Hankou Road,Nanjing,Jiangsu,China 210093;email:yinyt@nju.edu.cn. Permission to make digital or hard copies part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation.Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted.To copy otherwise,to republish,to post on servers, to redistribute to lists,or to use any component of this work in other works requires prior specific permission and/or a fee.Permissions may be requested from Publications Dept.,ACM,Inc.,2 Penn Plaza,Suite 701,New York,NY 10121-0701 USA,fax +1(212)869-0481,or permissions@acm.org ©2010ACM1942-3454/2010/11-ART1$10.00D0L:10.1145/1867719.1867720. http:/doi.acm.org/10.1145/1867719.1867720 ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010
1 Cell-Probe Proofs YITONG YIN Nanjing University We study the nondeterministic cell-probe complexity of static data structures. We introduce cellprobe proofs (CPP), a proof system for the cell-probe model, which describes verification instead of computation 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. —There exists a data structure problem with high nondeterministic cell-probe complexity. —For the exact nearest neighbor search (NNS) problem or the partial match problem in high dimensional Hamming space, for any data structure with Poly(n) cells, each of which contains O nC bits where C < 1, the nondeterministic cell-probe complexity is at least log(d/ log n) , where d is the dimension and n is the number of points in the data set. —For the polynomial evaluation problem of d-degree polynomial over finite field of size 2k where d ≤ 2k, for any data structure with s cells, each of which contains b bits, the nondeterministic cell-probe complexity is at least min k b (d − 1), k−log(d−1) log s . Categories and Subject Descriptors: E.1 [Data]: Data Structures; F.1.2 [Computation by Abstract Devices]: Modes of Computation General Terms: Theory Additional Key Words and Phrases: Cell-probe model, nondeterminism ACM Reference Format: Yin, Y. 2010. Cell-probe proofs. ACM Trans. Comput. Theory, 2, 1, Article 1 (November 2010), 17 pages. DOI = 10.1145/1867719.1867720. http://doi.acm.org/10.1145/1867719.1867720. 1. INTRODUCTION We study the problem of the nondeterministic cell-probe complexity of static data structures. This work was supported by the Program for New Century Excellent Talents at University (NCET) and by the National Science Foundation of China under grant 60721002. A preliminary version of this article appeared in the Proceedings of the 35th International Colloquium on Automata, Languages and Programming, pp. 72–83. Author’s address: Y. Yin, Nanjing University, Department of Computer Science and Technology, 22 Hankou Road, Nanjing, Jiangsu, China 210093; email: yinyt@nju.edu.cn. Permission to make digital or hard copies part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. c 2010 ACM 1942-3454/2010/11-ART1 $10.00 DOI: 10.1145/1867719.1867720. http://doi.acm.org/10.1145/1867719.1867720. 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 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 structure problem can be abstractly defined as a function f mapping each pair consisting 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 nondeterministic 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 computations, 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 complexity [Kushilevitz and Nisan 1997; Miltersen et al. 1998], for which the computations 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 different 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.
Cell-Probe Proofs ·1:3 Although nondeterministic cell-probe complexity is an important problem,the optimal nondeterministic bounds for static data structure problems are still un- known.For many naturally defined data structure problems,nondeterminism trivializes the problem in the sense that a constant number of nondeterministic cell-probes are sufficient to answer the queries.For the problems that remain nontrivial after allowing nondeterminism,no lower bounds are known for the 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 relatively high.More impor- tantly,it calls for a general technique to prove lower bounds on the nondeter- ministic cell-probe complexity of static data structures. 1.1 Our Contribution In this article.we initiate the study of nondeterministic cell-probe complexity for static data structures. We introduce cell-probe proofs,a proof system in the cell-probe model.This notion of proof corresponds to considering verification instead of computation in the cell-probe model.Unlike the fully adaptive computation in the tradi- tional cell-probe model,the formulation of cell-probe proofs shows a combinato- rial simplicity.We introduce a combinatorial structure that fully characterizes which problems have cell-probe proofs with specified parameters. With these novel tools,we show the following lower bounds on nondetermin- istic cell-probe complexity. -There exists a data structure problem with high nondeterministic cell-probe complexity.This result can be seen as a nondeterministic parallel to the existential lower bound for deterministic cell-probe complexity in Miltersen [1999],which is proved by counting.As mentioned in Miltersen [2008],the nondeterministic lower bound cannot be easily proved by the similar count- ing argument -For the exact nearest neighbor search(NNS)problem or the partial match problem in high dimensional Hamming space,for any data structure with Poly(n)cells,each of which contains O(nc)bits where C 1,the nonde- terministic cell-probe complexity is at least (log(d/logn)),where d is the dimension and n is the number of points in the data set.The highest known deterministic cell-probe lower bound for the problems for polynomial space is Q(d/logn)(see Barkol and Rabani [2002]and Patrascu [2008]).These lower bounds are proved by communication complexity techniques. -For the polynomial evaluation problem of d-degree polynomial over a fi- nite field of size 2 where d is high,for any data structure with s cells, each of which contains 6 bits,the nondeterministic cell-probe complex- ity is at least min 1).) This bound is nearly equal to the ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010
Cell-Probe Proofs · 1: 3 Although nondeterministic cell-probe complexity is an important problem, the optimal nondeterministic bounds for static data structure problems are still unknown. For many naturally defined data structure problems, nondeterminism trivializes the problem in the sense that a constant number of nondeterministic cell-probes are sufficient to answer the queries. For the problems that remain nontrivial after allowing nondeterminism, no lower bounds are known for the 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 relatively high. 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 article, we initiate the study of nondeterministic cell-probe complexity for static data structures. We introduce cell-probe proofs, a proof system in the cell-probe model. This notion of proof corresponds to considering verification instead of computation in the cell-probe model. Unlike the fully adaptive computation 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 cell-probe proofs with specified parameters. With these novel tools, we show the following lower bounds on nondeterministic cell-probe complexity. —There exists a data structure problem with high nondeterministic cell-probe complexity. This result can be seen as a nondeterministic parallel to the existential lower bound for deterministic cell-probe complexity in Miltersen [1999], which is proved by counting. As mentioned in Miltersen [2008], the nondeterministic lower bound cannot be easily proved by the similar counting argument. —For the exact nearest neighbor search (NNS) problem or the partial match problem in high dimensional Hamming space, for any data structure with Poly(n) cells, each of which contains O(nC) bits where C < 1, the nondeterministic cell-probe complexity is at least log d/ log n , where d is the dimension and n is the number of points in the data set. The highest known deterministic cell-probe lower bound for the problems for polynomial space is (d/ logn) (see Barkol and Rabani [2002] and Patras ˘ ¸cu [2008]). These lower bounds are proved by communication complexity techniques. —For the polynomial evaluation problem of d-degree polynomial over a fi- nite field of size 2k where d is high, for any data structure with s cells, each of which contains b bits, the nondeterministic cell-probe complexity is at least min k b (d − 1), k−log(d−1) log s . This bound is nearly equal to the ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.
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 powerful 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 nondeterministic lower bounds for certain dynamic data structure problems. This is formally 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 chronogram 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
Cell-Probe Proofs 1:5 Formally,a nondeterministic cell-probing algorithm is a function A which maps the query input x and the probed cells to the result value or L.such that for any query x and data y, (1)there exists a set of t cells in,i2,...,it,such that A(x,i,Ty(i》,(i2,T(i2),,,T()0=fx,y月 (2)for any set of t cells i,i2,...,it,it holds that A(x,1,Ty(i》,(i2,T,(i2)》,,(,T()》≠fx,y In order to formally characterize nondeterministic cell-probes for data struc- tures,we introduce a new concept,cell-probe proofs,which formalizes the notion of proof and verification in the cell-probe model.For a specific data structure problem f,a cell-probe proof system(CPP)may be defined for f as described in the following. We can think of a cell-probe proof system as a game played between an honest verifier and an untrusted prover.Both of them have unlimited com- putational power.Given an instance of data,a table of cells is honestly con- structed according to the rules known to both prover and verifier.Both the prover and the verifier know the query,but only the prover can observe the whole table and thus knows the data.The prover tries to convince the veri- fier about the result of the query to the data by revealing certain cells.After observing the revealed cells,the verifier either decides the correct answer,or rejects the proof,but cannot be tricked by the prover into returning a wrong answer. Formally,a cell-probe proof system(CPP)consists of three parts: -A table structure T:Y×I→{0，lb.For any data y,a table Ty:I→{0，lh is a mapping from indices of cells to their contents. -A prover P.For every x and y,Pxy I is a set of cells.We refer to Pxy as a proof and i,Ty(i)lie Pxy as a certificate. -A verifier v,which maps the queries with the certificates to the answers (0,1,L).Given an instance of data y,for any query x,both of the following conditions hold: (Completeness)Py I D(x,[i,T(i))li Pxy)=f(x,y),and (Soundness)P∈I:D(x,{iT,()Ii∈P})e{fx,y),⊥} An(s,b,t)-CPP is a CPP such that for every x and y:(1)the table has s cells, that is,I=s;(2)each cell contains b bits;and (3)each proof consists of t cell probes,that is,IPyl=t. Example.For the membership problem [Yao 1981],where X=[ml and Y ()and f)=1 if and only ify,a naive construction shows there is a 2-cell proof With a sorted table storing y,if x e y,the proof is the cell that contains x;ifx y,the proof consists of two consecutive cells which are the predecessor and successor of x.The same CPP also works for predecessor search Beame and Fich 2002]. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010
Cell-Probe Proofs · 1: 5 Formally, a nondeterministic cell-probing algorithm is a function A which maps the query input x and the probed cells to the result value or ⊥, such that for any query x and data y, (1) there exists a set of t cells i1,i2,...,it, such that A x, i1, Ty(i1) , i2, Ty(i2) ,..., it, Ty(it) = f(x, y); (2) for any set of t cells i1,i2,...,it, it holds that A x, i1, Ty(i1) , i2, Ty(i2) ,..., it, Ty(it) = f(x, y). In order to formally characterize nondeterministic cell-probes for data structures, we introduce a new concept, cell-probe proofs, which formalizes the notion of proof and verification in the cell-probe model. For a specific data structure problem f, a cell-probe proof system (CPP) may be defined for f as described in the following. We can think of a cell-probe proof system as a game played between an honest verifier and an untrusted prover. Both of them have unlimited computational power. Given an instance of data, a table of cells is honestly constructed according to the rules known to both prover and verifier. Both the prover and the verifier know the query, but only the prover can observe the whole table and thus knows the data. The prover tries to convince the veri- fier about the result of the query to the data by revealing certain cells. After observing the revealed cells, the verifier either decides the correct answer, or rejects the proof, but cannot be tricked by the prover into returning a wrong answer. Formally, a cell-probe proof system (CPP) consists of three parts: —A table structure T : Y × I → {0, 1}b . For any data y, a table Ty : I → {0, 1}b is a mapping from indices of cells to their contents. —A prover P. For every x and y, Pxy ⊆ I is a set of cells. We refer to Pxy as a proof and i, Ty(i) | i ∈ Pxy as a certificate. —A verifier v, which maps the queries with the certificates to the answers {0, 1, ⊥}. Given an instance of data y, for any query x, both of the following conditions hold: (Completeness) ∃Pxy ⊆ I : v x, i, Ty(i) | i ∈ Pxy = f(x, y), and (Soundness) ∀P ⊆ I : v x, i, Ty(i) | i ∈ P ∈ f(x, y), ⊥ . An (s, b,t)-CPP is a CPP such that for every x and y: (1) the table has s cells, that is, |I| = s; (2) each cell contains b bits; and (3) each proof consists of t cell probes, that is, |Pxy| = t. Example. For the membership problem [Yao 1981], where X = [m] and Y = [m] n , and f(x, y) = 1 if and only if x ∈ y, a naive construction shows there is a 2-cell proof. With a sorted table storing y, if x ∈ y, the proof is the cell that contains x; if x ∈ y, the proof consists of two consecutive cells which are the predecessor and successor of x. The same CPP also works for predecessor search [Beame and Fich 2002]. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.