{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:35:32Z","timestamp":1742913332610,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540705741"},{"type":"electronic","value":"9783540705758"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-3-540-70575-8_7","type":"book-chapter","created":{"date-parts":[[2008,8,12]],"date-time":"2008-08-12T16:07:43Z","timestamp":1218557263000},"page":"72-83","source":"Crossref","is-referenced-by-count":0,"title":["Cell-Probe Proofs and Nondeterministic Cell-Probe Complexity"],"prefix":"10.1007","author":[{"given":"Yitong","family":"Yin","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"4","key":"7_CR1","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1006\/jcss.2002.1831","volume":"64","author":"O. Barkol","year":"2002","unstructured":"Barkol, O., Rabani, Y.: Tighter lower bounds for nearest neighbor search and related problems in the cell probe model. Journal of Computer and System Sciences\u00a064(4), 873\u2013896 (2002)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"7_CR2","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1006\/jcss.2002.1822","volume":"65","author":"P. Beame","year":"2002","unstructured":"Beame, P., Fich, F.: Optimal bounds for the predecessor problem and related problems. Journal of Computer and System Sciences\u00a065(1), 38\u201372 (2002)","journal-title":"Journal of Computer and System Sciences"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Lower bounds for high dimensional nearest neighbor search and related problems. In: Proceedings of the thirty-first annual ACM Symposium on Theory of Computing, pp. 312\u2013321 (1999)","DOI":"10.1145\/301250.301330"},{"issue":"1","key":"7_CR4","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0304-3975(01)00144-X","volume":"288","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., de Wolf, R.: Complexity measures and decision tree complexity: a survey. Theoretical Computer Science\u00a0288(1), 21\u201343 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"4","key":"7_CR5","doi-asserted-by":"publisher","first-page":"932","DOI":"10.1137\/S0097539705447256","volume":"35","author":"E. Demaine","year":"2006","unstructured":"Demaine, E., P\u0103tra\u015fcu, M.: Logarithmic lower bounds in the cell-probe model. SIAM Journal of Computing\u00a035(4), 932\u2013963 (2006)","journal-title":"SIAM Journal of Computing"},{"key":"7_CR6","doi-asserted-by":"crossref","unstructured":"Fredman, M., Saks, M.: The cell probe complexity of dynamic data structures. In: Proceedings of the twenty-first annual ACM Symposium on Theory of Computing, pp. 345\u2013354 (1989)","DOI":"10.1145\/73007.73040"},{"key":"7_CR7","doi-asserted-by":"crossref","unstructured":"Husfeldt, T., Rauhe, T.: Hardness results for dynamic problems by extensions of Fredman and Saks\u2019 chronogram method. In: Proceedings of the 25th International Colloquium on Automata, Languages and Programming, pp. 67\u201378 (1998)","DOI":"10.1007\/BFb0055041"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Indyk, P., Goodman, J., O\u2019Rourke, J.: Nearest neighbors in high-dimensional spaces. In: Handbook of Discrete and Computational Geometry, ch. 39 (2004)","DOI":"10.1201\/9781420035315.ch39"},{"issue":"3","key":"7_CR9","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1016\/j.jcss.2004.04.006","volume":"69","author":"T. Jayram","year":"2004","unstructured":"Jayram, T., Khot, S., Kumar, R., Rabani, Y.: Cell-probe lower bounds for the partial match problem. Journal of Computer and System Sciences\u00a069(3), 435\u2013447 (2004)","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"7_CR10","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P. Miltersen","year":"1998","unstructured":"Miltersen, P., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. Journal of Computer and System Sciences\u00a057(1), 37\u201349 (1998)","journal-title":"Journal of Computer and System Sciences"},{"issue":"3","key":"7_CR11","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A. Yao","year":"1981","unstructured":"Yao, A.: Should tables be sorted? Journal of the ACM\u00a028(3), 615\u2013628 (1981)","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70575-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T03:32:45Z","timestamp":1714620765000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-540-70575-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9783540705741","9783540705758"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70575-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2008]]}}}