Cell-Probe Proofs YITONG YIN Nanjing University We study the nondeterministic cell-probe complexity of static data structures.We introduce cell. probe proofs (CPP),a proof system for the cell-probe model,which describes verification instead of computation in the cell-probe model.We present a combinatorial characterization of CPP.With this novel tool,we prove the following lower bounds for the nondeterministic cell-probe complexity of static data structures. -There exists a data structure problem with high nondeterministic cell-probe complexity. -For the exact nearest neighbor search(NNS)problem or the partial match problem in high di- mensional Hamming space,for any data structure with Poly(n)cells,each of which contains O(nc)bits where C 1,the nondeterministic cell-probe complexity is at least (log(d/logn)). where d is the dimension and n is the number of points in the data set. -For the polynomial evaluation problem of d-degree polynomial over finite field of size 2k where ds 2,for any data structure with s cells,each of which contains b bits,the nondeterministic cell-probe complexity is at least min ((d-1). 10g8 Categories and Subject Descriptors:E.1 [Datal:Data Structures;F.1.2 [Computation by Abstract Devices]:Modes of Computation General Terms:Theory Additional Key Words and Phrases:Cell-probe model,nondeterminism ACM Reference Format: Yin,Y.2010.Cell-probe proofs.ACM Trans.Comput.Theory,2,1,Article 1(November 2010), 17 pages..D0I-10.1145/1867719.1867720.http/doi.acm.org/10.1145/1867719.1867720. 1.INTRODUCTION We study the problem of the nondeterministic cell-probe complexity of static data structures. This work was supported by the Program for New Century Excellent Talents at University(NCET) and by the National Science Foundation of China under grant 60721002. A preliminary version of this article appeared in the Proceedings of the 35th International Collo. quium on Automata,Languages and Programming,pp.72-83. Author's address:Y.Yin,Nanjing University,Department of Computer Science and Technology,22 Hankou Road,Nanjing,Jiangsu,China 210093;email:yinyt@nju.edu.cn. Permission to make digital or hard copies part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation.Copyrights for components of this work owned by others than ACM must be honored.Abstracting with credit is permitted.To copy otherwise,to republish,to post on servers, to redistribute to lists,or to use any component of this work in other works requires prior specific permission and/or a fee.Permissions may be requested from Publications Dept.,ACM,Inc.,2 Penn Plaza,Suite 701,New York,NY 10121-0701 USA,fax +1(212)869-0481,or permissions@acm.org ©2010ACM1942-3454/2010/11-ART1$10.00D0L:10.1145/1867719.1867720. http:/doi.acm.org/10.1145/1867719.1867720 ACM Transactions on Computation Theory,Vol.2,No.1,Article 1,Pub.date:November 2010.1 Cell-Probe Proofs YITONG YIN Nanjing University We study the nondeterministic cell-probe complexity of static data structures. We introduce cell￾probe proofs (CPP), a proof system for the cell-probe model, which describes verification instead of computation in the cell-probe model. We present a combinatorial characterization of CPP. With this novel tool, we prove the following lower bounds for the nondeterministic cell-probe complexity of static data structures. —There exists a data structure problem with high nondeterministic cell-probe complexity. —For the exact nearest neighbor search (NNS) problem or the partial match problem in high di￾mensional Hamming space, for any data structure with Poly(n) cells, each of which contains O nC bits where C < 1, the nondeterministic cell-probe complexity is at least log(d/ log n) , where d is the dimension and n is the number of points in the data set. —For the polynomial evaluation problem of d-degree polynomial over finite field of size 2k where d ≤ 2k, for any data structure with s cells, each of which contains b bits, the nondeterministic cell-probe complexity is at least min  k b (d − 1), k−log(d−1) log s  . Categories and Subject Descriptors: E.1 [Data]: Data Structures; F.1.2 [Computation by Abstract Devices]: Modes of Computation General Terms: Theory Additional Key Words and Phrases: Cell-probe model, nondeterminism ACM Reference Format: Yin, Y. 2010. Cell-probe proofs. ACM Trans. Comput. Theory, 2, 1, Article 1 (November 2010), 17 pages. DOI = 10.1145/1867719.1867720. http://doi.acm.org/10.1145/1867719.1867720. 1. INTRODUCTION We study the problem of the nondeterministic cell-probe complexity of static data structures. This work was supported by the Program for New Century Excellent Talents at University (NCET) and by the National Science Foundation of China under grant 60721002. A preliminary version of this article appeared in the Proceedings of the 35th International Collo￾quium on Automata, Languages and Programming, pp. 72–83. Author’s address: Y. Yin, Nanjing University, Department of Computer Science and Technology, 22 Hankou Road, Nanjing, Jiangsu, China 210093; email: yinyt@nju.edu.cn. Permission to make digital or hard copies part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies show this notice on the first page or initial screen of a display along with the full citation. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works requires prior specific permission and/or a fee. Permissions may be requested from Publications Dept., ACM, Inc., 2 Penn Plaza, Suite 701, New York, NY 10121-0701 USA, fax +1 (212) 869-0481, or permissions@acm.org. c 2010 ACM 1942-3454/2010/11-ART1 $10.00 DOI: 10.1145/1867719.1867720. http://doi.acm.org/10.1145/1867719.1867720. ACM Transactions on Computation Theory, Vol. 2, No. 1, Article 1, Pub. date: November 2010.