Cel-Probe Proofs·1:9 Therefore,each h with the desirable property Q(h)corresponds to a distinct pair of members in IF).According to the definition of x(s,t),the total number of the h that Q(h)holds is upper bounded by x(s,t).There are totally 22"differenth:Y→{0，ll.Therefore, ≤x(s,t02-2 Let f be a uniformly random function f:X×Y→{0，l,it holds that X PF[xeX,Qfx,川s(RrQh） ≤(a.t02-22. There are at most 2s2 different s x 2-partitions of Y.By union bound,for uni- formly random f:X×Y→{0，l,with probability at most(x(s,t02-2)222 there exists an s x 2-partition F of Y such that for allxe X and yY,there exists A∈I(F)y)such that|f(x,A)川=1. Due to Theorem 3.2,it holds that the probability that there exists an (s,1,t)-CPP for a uniformly random f:(0,1)m x (0,1)"(0,1]is at most (x(s,t)2-2)2252.Statement 1 is proved. If(),then ((s))1.With positive probability, a uniformly random f has no(s,1,t)-CPP.There must exist a data structure problem without(s,1,t)-CPP.Statement 2 holds. The following lemma gives an estimation of the parameter x(s,t). LEMMA 4.2.If ≤2-) then it holds that y(s,t)<22"(1-s12m) PROOF.For any s x 2-partition F of Y,I(F)is a l x k-partition of y, where l≤（食andk≤2，thus|I(F)≤（图2.Note that the cardi- nality of the union closure of a set system is upper bounded by the car- dinality of its power set.Therefore,for any s x 2-partition F of Y,it holds that(F)s 2-1+()2<22"d-/2"),which means that x(s.)< 22™(1-s/2m) ▣ Combining the above two lemmas,we have the following theorem. THEOREM4.3.If(月2≤2m(1-品)，there exists a problem f：{0,1m× (0,1)"(0,1)such that there does not exist (s,1,t)-CPP for f. Applying the above theorem to specific s,t,m,and n,we can see that there exists nondeterministically hard problem for some usual settings of these parameters. -s=2m-1 and t<m;so the size of the data structure is one bit less than the naive solution of storing answers to all queries,and the size of the proof is less thanof the size of a raw data instance. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.Cell-Probe Proofs · 1: 9 Therefore, each h with the desirable property Q(h) corresponds to a distinct pair of members in ∗ It(F). According to the definition of χ(s,t), the total number of the h that Q(h) holds is upper bounded by χ(s,t). There are totally 22n different h : Y → {0, 1}. Therefore, Pr h [Q(h)] ≤ 1 2 ∗ It(F) /22n ≤ χ(s,t)2−2n . Let f be a uniformly random function f : X × Y → {0, 1}, it holds that Pr f  ∀x ∈ X, Q( f(x,·)) ≤  Pr h [Q(h)]|X| ≤ χ(s,t)2−2n 2m . There are at most 2s2n different s × 2-partitions of Y. By union bound, for uni￾formly random f : X × Y → {0, 1}, with probability at most χ(s,t)2−2n 2m 2s2n , there exists an s × 2-partition F of Y such that for all x ∈ X and y ∈ Y, there exists A ∈ It(F)(y) such that f(x, A) = 1. Due to Theorem 3.2, it holds that the probability that there exists an (s, 1,t)-CPP for a uniformly random f : {0, 1}m × {0, 1}n → {0, 1} is at most (χ(s,t)2−2n ) 2m 2s2n . Statement 1 is proved. If χ(s,t) < 22n(1−s/2m) , then χ(s,t)2−2n 2m 2s2n < 1. With positive probability, a uniformly random f has no (s, 1,t)-CPP. There must exist a data structure problem without (s, 1,t)-CPP. Statement 2 holds. The following lemma gives an estimation of the parameter χ(s,t). LEMMA 4.2. If  s t  2t ≤ 2n  1 − s 2m  , then it holds that χ(s,t) < 22n(1−s/2m) . PROOF. For any s × 2-partition F of Y, It(F) is a l × k-partition of Y, where l ≤ s t and k ≤ 2t , thus It(F) ≤ s t 2t . Note that the cardi￾nality of the union closure of a set system is upper bounded by the car￾dinality of its power set. Therefore, for any s × 2-partition F of Y, it holds that 1 2 ∗ It(F) ≤ 2−1+( s t)2t < 22n(1−s/2m) , which means that χ(s,t) < 22n(1−s/2m) . Combining the above two lemmas, we have the following theorem. THEOREM 4.3. If s t 2t ≤ 2n 1 − s 2m , there exists a problem f : {0, 1}m × {0, 1}n → {0, 1} such that there does not exist (s, 1,t)-CPP for f. Applying the above theorem to specific s, t, m, and n, we can see that there exists nondeterministically hard problem for some usual settings of these parameters. —s = 2m − 1 and t < n m; so the size of the data structure is one bit less than the na¨ıve solution of storing answers to all queries, and the size of the proof is less than 1 m of the size of a raw data instance. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.