Cell-Probe Proofs
ACM Transactions on Computation Theory · 2010
DOI: 10.1145/1867719.1867720 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Computation Theory, 2010. Verfasst von Yitong Yin. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 17 Literaturangaben. Gefördert von: National Natural Science Foundation of China.
Abstract (Originalsprache)
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 dimensional Hamming space, for any data structure with Poly( n ) cells, each of which contains O ( n C ) 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 2 k where d ≤ 2 k , 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 )).
Förderung
- National Natural Science Foundation of China
Zitieren
APA
Yin, Y. (2010). Cell-Probe Proofs. ACM Transactions on Computation Theory. https://doi.org/10.1145/1867719.1867720
Vancouver
Yin Y. Cell-Probe Proofs. ACM Transactions on Computation Theory. 2010. doi:10.1145/1867719.1867720
BibTeX
@article{Yin2010,
author = {Yin, Yitong},
title = {Cell-Probe Proofs},
journal = {ACM Transactions on Computation Theory},
year = {2010},
doi = {10.1145/1867719.1867720}
}
EUVIMED