Cell-Probe Proofs 1:5 Formally,a nondeterministic cell-probing algorithm is a function A which maps the query input x and the probed cells to the result value or L.such that for any query x and data y, (1)there exists a set of t cells in,i2,...,it,such that A(x,i,Ty(i》,(i2,T(i2),,,T()0=fx,y月 (2)for any set of t cells i,i2,...,it,it holds that A(x,1,Ty(i》,(i2,T,(i2)》,,(,T()》≠fx,y 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 proof and verification 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 in the following. 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 com- putational power.Given an instance of data,a table of cells is honestly con- structed 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 veri- fier 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 cannot 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，lb.For any data y,a table Ty:I→{0，lh 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 i,Ty(i)lie Pxy 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 x,both of the following conditions hold: (Completeness)Py I D(x,[i,T(i))li Pxy)=f(x,y),and (Soundness)P∈I:D(x,{iT,()Ii∈P})e{fx,y),⊥} An(s,b,t)-CPP is a CPP such that for every x and y:(1)the table has s cells, that is,I=s;(2)each cell contains b bits;and (3)each proof consists of t cell probes,that is,IPyl=t. Example.For the membership problem [Yao 1981],where X=[ml and Y ()and f)=1 if and only ify,a naive construction shows there is a 2-cell proof With a sorted table storing y,if x e y,the proof is the cell that contains x;ifx y,the proof consists of two consecutive cells which are the predecessor and successor of x.The same CPP also works for predecessor search Beame and Fich 2002]. ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.Cell-Probe Proofs · 1: 5 Formally, a nondeterministic cell-probing algorithm is a function A which maps the query input x and the probed cells to the result value or ⊥, such that for any query x and data y, (1) there exists a set of t cells i1,i2,...,it, such that A x,  i1, Ty(i1)  ,  i2, Ty(i2)  ,..., it, Ty(it)  = f(x, y); (2) for any set of t cells i1,i2,...,it, it holds that A x,  i1, Ty(i1)  ,  i2, Ty(i2)  ,..., it, Ty(it)  = f(x, y). 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 proof and verification 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 in the following. 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 com￾putational power. Given an instance of data, a table of cells is honestly con￾structed 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 veri- fier 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 cannot 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 i, Ty(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, i, Ty(i)  | i ∈ Pxy = f(x, y), and (Soundness) ∀P ⊆ I : v x, i, Ty(i)  | i ∈ P ∈  f(x, y), ⊥ . An (s, b,t)-CPP is a CPP such that for every x and y: (1) the table has s cells, that is, |I| = s; (2) each cell contains b bits; and (3) each proof consists of t cell probes, that is, |Pxy| = t. Example. For the membership problem [Yao 1981], where X = [m] and Y = [m] n , and f(x, y) = 1 if and only if x ∈ y, a naive construction shows there is a 2-cell proof. With a sorted table storing y, if x ∈ y, the proof is the cell that contains x; if x ∈ y, the proof consists of two consecutive cells which are the predecessor and successor of x. The same CPP also works for predecessor search [Beame and Fich 2002]. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.