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 re￾turns that value, otherwise it returns “⊥”. 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. 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 char￾acterization 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 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 : 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.