1:6·Y.Yin The fact that this simple example also works for predecessor has an impor- tant implication.Combining with the super-constant lower bound for predeces- sor search [Patrascu and Thorup 2006],this gives an example where one can separate deterministic and nondeterministic complexity. We remark that cell-probe proofs characterize the nondeterministic probes in the cell-probe model.Specifically,the verifier o is just a nondeterministic cell-probing algorithm.It is natural to see that for a cell-probe scheme,for any query,the cells probed by an adaptive algorithm contain a cell-probe proof. This can be seen as a data structure counterpart of P NP. It is important to note that although a data structure problem is nothing but a boolean function,CPP is very different from the certificate complexity of boolean functions [Buhrman and de Wolf 2002].In CPP,the prover and the verifier communicate with each other via a table structure,which distinguishes CPP from standard certificate complexity.For any data structure problem,the table structure can always store the results for all queries,making one cell- probe sufficient to prove the result,which is generally impossible in the model of certificate complexity. We should also be specific that the model of cell-probe proofs prohibits ran- domization.The nondeterministic model for randomized data structures is a possible future direction. Unlike adaptive cell-probes,CPP has a static nature,which is convenient for reductions.As stated by the following lemma,any CPP can be trivially reduced to 1-cell proofs. LEMMA 2.1 REDUCTION LEMMA.For any data structure problem f,if there exists an (s,b,t)-CPP,then there exists an (st,bt,1)-CPP. PROOF.Just store every t-tuple of cells in the(s,b,t)-CPP as a new cell in the (sf,bt,1)-CPP. ▣ 3.CHARACTERIZATION OF CPPS We now introduce a combinatorial characterization of CPP.Given a set system FC2Y,for any yY,we let F(y)=(FEFIy e F).For convenience,for a partition P of y,we abuse this notation and let P(y)denote the set FeP that y∈F. Definition 3.1.We say a set system FC2Y is an s x k-partition of y if F is a union ofs many partitions of y,where the cardinality of each partition is at most k. This particular notion of partitions of y fully captures the structure of cell- probe proofs.The following theorem provides a full characterization of cell- probe proofs. THEOREM3.2.There is an(s,b,t)-CPP for f:X×Y→{0,1}，if and only if there exists an s x 26-partition F of Y,such that for every x e X and every yeY,there exist F1,...,FeF(y)such that f(x,F)=1. PROOF.First,we prove the“only if”part. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010
1: 6 · Y. Yin The fact that this simple example also works for predecessor has an important implication. Combining with the super-constant lower bound for predecessor search [Patras ˘ ¸cu and Thorup 2006], this gives an example where one can separate deterministic and nondeterministic complexity. We remark that cell-probe proofs characterize the nondeterministic probes in the cell-probe model. Specifically, the verifier v is just a nondeterministic cell-probing algorithm. It is natural to see that for a cell-probe scheme, for any query, the cells probed by an adaptive algorithm contain a cell-probe proof. This can be seen as a data structure counterpart of P ⊆ NP. It is important to note that although a data structure problem is nothing but a boolean function, CPP is very different from the certificate complexity of boolean functions [Buhrman and de Wolf 2002]. In CPP, the prover and the verifier communicate with each other via a table structure, which distinguishes CPP from standard certificate complexity. For any data structure problem, the table structure can always store the results for all queries, making one cellprobe sufficient to prove the result, which is generally impossible in the model of certificate complexity. We should also be specific that the model of cell-probe proofs prohibits randomization. The nondeterministic model for randomized data structures is a possible future direction. Unlike adaptive cell-probes, CPP has a static nature, which is convenient for reductions. As stated by the following lemma, any CPP can be trivially reduced to 1-cell proofs. LEMMA 2.1 REDUCTION LEMMA. For any data structure problem f, if there exists an (s, b,t)-CPP, then there exists an (st , b t, 1)-CPP. PROOF. Just store every t-tuple of cells in the (s, b,t)-CPP as a new cell in the (st , b t, 1)-CPP. 3. CHARACTERIZATION OF CPPS We now introduce a combinatorial characterization of CPP. Given a set system F ⊆ 2Y , for any y ∈ Y, we let F(y) = {F ∈ F | y ∈ F}. For convenience, for a partition P of Y, we abuse this notation and let P(y) denote the set F ∈ P that y ∈ F. Definition 3.1. We say a set system F ⊆ 2Y is an s × k-partition of Y if F is a union of s many partitions of Y, where the cardinality of each partition is at most k. This particular notion of partitions of Y fully captures the structure of cellprobe proofs. The following theorem provides a full characterization of cellprobe proofs. THEOREM 3.2. There is an (s, b,t)-CPP for f : X × Y → {0, 1}, if and only if there exists an s × 2b -partition F of Y, such that for every x ∈ X and every y ∈ Y, there exist F1,..., Ft ∈ F(y) such that f(x,∩t i=1Fi) = 1. PROOF. First, we prove the “only if ” part. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010
Cell-Probe Proofs ·1:7 LetT:Y×s→{0，l]6 be the table structure in the(s,b,t)-CPpP. Define the map of the table structure as an s x 25 matrix M such that Mii=ly e Y I T(i)=il,that is,Mii is the set of all such data instances y that the content of the i-th cell of the table is j,assuming that the data instance is y.It is easy to verify that (Miil is an s x 25-partition of Y. We then show that for every xe X and y e Y,there must exist i,i2,...,it such that f(x,M(i,j))=1,where j=T(i).To the contrary,we assume that for some x,there exists such y that for all i1,i2,...,i,there always exists y'eM(i,T())such that f(x,y)f(x,y).According to the definition of M,it implies that for any i,i2,...,it,there exists a y that shares the same certificate [i,T,(i)Ik=1,2,...,t}with y,but f(x,y)f(x,y). Due to the completeness of CPP,the verifier maps one of the certificates i,T(i)k=1,2,...,th of y to f(x,y),but in this case the adversary can choose y'as the real data instance,contradicting the soundness of the CPP. We then deal with the "if"part. Let F be an s x 25-partition of Y such that for every x and every y there is an Fe F(y)that f(x,F)=1.We rewrite F as an s x 25 matrix M such that Mii is indexed as the ith partition set in the ith partition in F,that is, (Mijlij=F and for any i,(Miilj is a partition of y. We can define the table structure T:Y x [s](0,1]5 as follows:T(i)is assigned with the unique jthat ye Mij. The verifier is defined as follows:for any xX and any certificate {(i,Ik=1,2,...,t),if f(x,)is constant onM(is,j),then the verifier re- turns that value,otherwise it returns"L".It is easy to verify that both the com- pleteness and soundness of CPP are satisfied. ▣ For all CPPs,one-cell proofs are the simplest nontrivial proofs.As we ex- plained in the last section,the case of a one-cell proof is also very important because all CPPs can be reduced to it.We apply the above theorem to the one-cell case in the following corollary. COROLLARY3.3.There is an(sb,1)-CPP for f:X×Y→{0,1}，if and only if there exists an sx2b-partition F of Y,such that for every x e X and every yY,there is an FeF(y)that f(x,F)=1. Let Yo=(y eY I f(x,y)=0)and Yi=(y EY I f(x,y)=1).An alternative char- acterization is that there is a(s,b,l)-CPP for a problem f:X×Y→{0，l, if and only if there exists an s x 25-partition F of y such that (Yo,Yilxex is contained by the union-closure of F.It can easily be noted that this character- ization is equivalent to the one in Corollary 3.3.With this formulation,we get some intuition about 1-cell proofs;that is,a problem f:Xx Y>(0,1)has simple proofs,if and only if there exists some set system F2 with a simple structure such that the complexity ofF matches the complexity of the problem. 4.AN EXISTENTIAL LOWER BOUND In this section we prove an existential lower bound for cell-probe proofs by showing that uniformly random data structure problem has no efficient CPP ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010
Cell-Probe Proofs · 1: 7 Let T : Y × [s] → {0, 1}b be the table structure in the (s, b,t)-CPP. Define the map of the table structure as an s × 2b matrix M such that Mij = {y ∈ Y | Ty(i) = j}, that is, Mij is the set of all such data instances y that the content of the i-th cell of the table is j, assuming that the data instance is y. It is easy to verify that {Mij} is an s × 2b -partition of Y. We then show that for every x ∈ X and y ∈ Y, there must exist i1,i2,...,it such that f x,∩t k=1M (ik, jk) = 1, where jk = Ty(ik). To the contrary, we assume that for some x, there exists such y that for all i1,i2,...,it, there always exists y ∈ ∩t k=1M ik, Ty(ik) such that f(x, y) = f(x, y ). According to the definition of M, it implies that for any i1,i2,...,it, there exists a y that shares the same certificate ik, Ty(ik) | k = 1, 2,...,t with y, but f(x, y ) = f(x, y). Due to the completeness of CPP, the verifier maps one of the certificates ik, Ty(ik) | k = 1, 2,...,t of y to f(x, y), but in this case the adversary can choose y as the real data instance, contradicting the soundness of the CPP. We then deal with the “if ” part. Let F be an s × 2b -partition of Y such that for every x and every y there is an F ∈ F(y) that f(x, F) = 1. We rewrite F as an s × 2b matrix M such that Mij is indexed as the jth partition set in the ith partition in F, that is, {Mij}i, j = F and for any i, {Mij}j is a partition of Y. We can define the table structure T : Y × [s] → {0, 1} b as follows: Ty(i) is assigned with the unique j that y ∈ Mij. The verifier is defined as follows: for any x ∈ X and any certificate { ik, jk | k = 1, 2,...,t}, if f(x,·) is constant on ∩t k=1M(ik, jk), then the verifier returns that value, otherwise it returns “⊥”. It is easy to verify that both the completeness and soundness of CPP are satisfied. For all CPPs, one-cell proofs are the simplest nontrivial proofs. As we explained in the last section, the case of a one-cell proof is also very important because all CPPs can be reduced to it. We apply the above theorem to the one-cell case in the following corollary. COROLLARY 3.3. There is an (s, b, 1)-CPP for f : X × Y → {0, 1}, if and only if there exists an s × 2b -partition F of Y, such that for every x ∈ X and every y ∈ Y, there is an F ∈ F(y) that | f(x, F)| = 1. Let Yx 0 = {y ∈ Y | f(x, y)=0} and Yx 1 = {y ∈ Y | f(x, y)=1}. An alternative characterization is that there is a (s, b, 1)-CPP for a problem f : X × Y → {0, 1}, if and only if there exists an s × 2b -partition F of Y such that {Yx 0,Yx 1}x∈X is contained by the union-closure of F. It can easily be noted that this characterization is equivalent to the one in Corollary 3.3. With this formulation, we get some intuition about 1-cell proofs; that is, a problem f : X × Y → {0, 1} has simple proofs, if and only if there exists some set system F ⊆ 2Y with a simple structure such that the complexity of F matches the complexity of the problem. 4. AN EXISTENTIAL LOWER BOUND In this section we prove an existential lower bound for cell-probe proofs by showing that uniformly random data structure problem has no efficient CPP ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.