Yitong Yin lower bounds,we only consider decision problems.We refer to each y E Y as data and each rE X as a query.For each pair of r and y,f(,y)specifies the result of the query r to the data structure that represents the data y. In the cell-probe model (c.f.[11,6]),the data instance y is preprocessed and stored in cells,and for each query z,the value of f(r,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，l}6 specifies a table T:I{0,1]for each data instance y,which maps indices of cells to their contents.Given a query r,the query algorithm makes a sequence of probes i1,i2,...to the cells,where ik depends on x and all previous cell probes (i1,T(i)),(i2,T(i2)),...,(ik-1,T(ik-1)).The value of f(r,y)is decided at last based on the collected information. In this work,we focus on nondeterministic cell-probes.Given a query z to a data instance y,a set of t cells i1,i2,...,it are probed nondeterministi- cally,such that the value of f(,y)is decided based on the probed information (i1,Ty(i1)》,(2,Ty(i2)》,,(it,Ty(it)》. 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 proofs and verifications 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 below. 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 computa- tional 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 verifier 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 can not 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，l}b.For any data,a table T:I→{0,1b is a mapping from indices of cells to their contents. -A prover P.For every x and y,Pry CI is a set of cells.We refer to Pry as a proof and {(i,T(i))|iE Pry}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 z,both of the following conditions hold: (Completeness)3Py≤I:v(a,{i,Tg(i)》li∈Pxy})=f(x,y),and (Soundnes）P'cI:e,{k,T,(》lieP')={ 了f(x,) An (s,b,t)-CPP is a CPP such that for every x and y:(1)the table has s cells,i.e.I=s;(2)each cell contains b bits;(3)each proof consists of t cell probes,i.e.Prul =t.4 Yitong Yin lower bounds, we only consider 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. [11, 6]), 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 hi1, Ty(i1)i,hi2, Ty(i2)i, . . . ,hik−1, Ty(ik−1)i. 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 nondeterministi￾cally, such that the value of f(x, y) is decided based on the probed information hi1, Ty(i1)i,hi2, Ty(i2)i, . . . ,hit, Ty(it)i. 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 proofs and verifications 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 below. 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 computa￾tional 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 verifier 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 can not 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 {hi, Ty(i)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, {hi, Ty(i)i | i ∈ Pxy}) = f(x, y), and (Soundness) ∀P 0 ⊆ I : v(x, {hi, Ty(i)i | i ∈ P 0}) =  f(x, y) ⊥ . An (s, b, t)-CPP is a CPP such that for every x and y: (1) the table has s cells, i.e. |I| = s; (2) each cell contains b bits; (3) each proof consists of t cell probes, i.e. |Pxy| = t