1:8.Y.Yin with high probability,which means that for most data structure problems, there does not exist efficient nondeterministic data structures.Like the ex- istential lower bound for deterministic data structures in Miltersen [1999],our lower bound is in the form of bit-probe complexity,that is,each cell contains only one bit. We first introduce some notations. -Given a set family F,we denote that AilA1,A2.....A. We call IF)the t-intersection closure of F. Similarly,we define the union closure of a set system F as U'F= UAIF),which is a set of all the unions of the members of F. -For a fixed a set Y of data instances,we define the parameter x(s,t)as the smallest integer that for every s x 2-partition F of Y,x(s,t)I(F). The value x(s,t)depends on s,t,and the size of Y. The following lemma shows a relation between thethe parameter x(s,t)and the existence of hard problems. LEMMA4.l.Letf:X×Y→{0，l)be a data structure problem where X= (0,1ym is the set of queries and Y =(0,1y"is the set of data instances.The following statements hold: (1)With probability at least 1-(x(s,t)2-2)222,there does not exists an (s,1,t)-CPP for uniformly random f:XxY(0,1). (2)If x(st)<),then there exists a problem f such that there does not exist an (s,1,t)-CPP for f. PROOF.We first prove 1.Then 2 follows naturally. Let F be an s×2-partition of y and h:y→{0，l}be a uniformly random 2-coloring of Y.We evaluate the probability that for ally e Y,there exists some A I(F)such that y e A and h is constant over A.Let Q(h)be a predicate defined on h:Y→{0，l}such that Q(h)is true iffVy∈Y,3A∈I(F)y),lh(AI= 1.The probability is Pr[Q(h)]. If Q(h)holds,it must hold that there exist Bo,B1(F)such that (Bo,B1)is a bipartition of Y.In fact,given an h:Y(0,1)such that Vy e Y, Ay I(F)(y),h(Ay)=1,we can construct such Bo and Bi as Bo=Ay,and B1=Ay. y:h(y=0 y:h(y)=1 It is easy to check that (Bo,B1)CUI(F)is a bipartition of Y and h(B)=(b} forb∈{0,1. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.1: 8 · Y. Yin with high probability, which means that for most data structure problems, there does not exist efficient nondeterministic data structures. Like the ex￾istential lower bound for deterministic data structures in Miltersen [1999], our lower bound is in the form of bit-probe complexity, that is, each cell contains only one bit. We first introduce some notations. —Given a set family F, we denote that It(F) =  t i=1 Ai | A1, A2,..., At ∈ F . We call It(F) the t-intersection closure of F. —Similarly, we define the union closure of a set system F as ∗ F =  A∈G A | G ⊆ F , which is a set of all the unions of the members of F. —For a fixed a set Y of data instances, we define the parameter χ(s,t) as the smallest integer that for every s × 2-partition F of Y, χ(s,t) ≥ 1 2 ∗ It(F) . The value χ(s,t) depends on s, t, and the size of Y. The following lemma shows a relation between the the parameter χ(s,t) and the existence of hard problems. LEMMA 4.1. Let f : X × Y → {0, 1} be a data structure problem where X = {0, 1}m is the set of queries and Y = {0, 1}n is the set of data instances. The following statements hold: (1) With probability at least 1 − χ(s,t)2−2n 2m 2s2n , there does not exists an (s, 1,t)-CPP for uniformly random f : X × Y → {0, 1}. (2) If χ(s,t) < 22n(1−s/2m) , then there exists a problem f such that there does not exist an (s, 1,t)-CPP for f. PROOF. We first prove 1. Then 2 follows naturally. Let F be an s × 2-partition of Y and h : Y → {0, 1} be a uniformly random 2-coloring of Y. We evaluate the probability that for all y ∈ Y, there exists some A ∈ It(F) such that y ∈ A and h is constant over A. Let Q(h) be a predicate defined on h : Y → {0, 1} such that Q(h) is true iff ∀y ∈ Y, ∃A ∈ It(F)(y),|h(A)| = 1. The probability is Prh[Q(h)]. If Q(h) holds, it must hold that there exist B0, B1 ∈ ∗ It(F) such that {B0, B1} is a bipartition of Y. In fact, given an h : Y → {0, 1} such that ∀y ∈ Y, ∃Ay ∈ It(F)(y), h(Ay) = 1, we can construct such B0 and B1 as B0 =  y:h(y)=0 Ay, and B1 =  y:h(y)=1 Ay. It is easy to check that {B0, B1} ⊂ ∗ It(F) is a bipartition of Y and h(Bb ) = {b} for b ∈ {0, 1}. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.