{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:44:43Z","timestamp":1725795883145},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662439470"},{"type":"electronic","value":"9783662439487"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-662-43948-7_86","type":"book-chapter","created":{"date-parts":[[2014,6,11]],"date-time":"2014-06-11T12:10:36Z","timestamp":1402488636000},"page":"1039-1050","source":"Crossref","is-referenced-by-count":1,"title":["Certificates in Data Structures"],"prefix":"10.1007","author":[{"given":"Yaoyu","family":"Wang","sequence":"first","affiliation":[]},{"given":"Yitong","family":"Yin","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"86_CR1","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P., P\u01cetra\u015fcu, M.: On the optimality of the dimensionality reduction method. In: Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 449\u2013458 (2006)","DOI":"10.1109\/FOCS.2006.56"},{"issue":"4","key":"86_CR2","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"},{"key":"86_CR3","doi-asserted-by":"crossref","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Lower bounds for high dimensional nearest neighbor search and related problems. In: Proc. 31st ACM Symposium on Theory of Computing (STOC), pp. 312\u2013321 (1999)","DOI":"10.1145\/301250.301330"},{"key":"86_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BFb0055041","volume-title":"Automata, Languages and Programming","author":"T. Husfeldt","year":"1998","unstructured":"Husfeldt, T., Rauhe, T.: Hardness results for dynamic problems by extensions of fredman and saks\u2019 chronogram method. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol.\u00a01443, pp. 67\u201378. Springer, Heidelberg (1998)"},{"issue":"4","key":"86_CR5","doi-asserted-by":"publisher","first-page":"627","DOI":"10.1006\/jcss.2001.1781","volume":"63","author":"P. Indyk","year":"2001","unstructured":"Indyk, P.: On approximate nearest neighbors under \u2113\u2009\u221e\u2009 norm. Journal of Computer and System Sciences\u00a063(4), 627\u2013638 (2001)","journal-title":"Journal of Computer and System Sciences"},{"key":"86_CR6","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Khot, S., Kumar, R., Rabani, Y.: Cell-probe lower bounds for the partial match problem. In: Proc. 35th ACM Symposium on Theory of Computing (STOC), pp. 667\u2013672 (2003)","DOI":"10.1145\/780637.780639"},{"key":"86_CR7","doi-asserted-by":"crossref","unstructured":"Larsen, K.G.: Higher cell probe lower bounds for evaluating polynomials. In: Proc. 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 293\u2013301 (2012)","DOI":"10.1109\/FOCS.2012.21"},{"issue":"1","key":"86_CR8","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.ipl.2004.06.001","volume":"92","author":"D. Liu","year":"2004","unstructured":"Liu, D.: A strong lower bound for approximate nearest neighbor searching. Information Processing Letters\u00a092(1), 23\u201329 (2004)","journal-title":"Information Processing Letters"},{"issue":"1","key":"86_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P.B. Miltersen","year":"1998","unstructured":"Miltersen, P.B., 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"},{"key":"86_CR10","doi-asserted-by":"crossref","unstructured":"Panigrahy, R., Talwar, K., Wieder, U.: A geometric approach to lower bounds for approximate near-neighbor search and partial match. In: Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 414\u2013423 (2008)","DOI":"10.1109\/FOCS.2008.68"},{"key":"86_CR11","doi-asserted-by":"crossref","unstructured":"Panigrahy, R., Talwar, K., Wieder, U.: Lower bounds on near neighbor search via metric expansion. In: Proc. 51th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 805\u2013814 (2010)","DOI":"10.1109\/FOCS.2010.82"},{"key":"86_CR12","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Lower bounds for 2-dimensional range counting. In: Proc. 30th ACM Symposium on Theory of Computing (STOC), pp. 40\u201346 (2007)","DOI":"10.1145\/1250790.1250797"},{"key":"86_CR13","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M.: Unifying the landscape of cell-probe lower bounds. SIAM Journal on Computing 40(3), 827\u2013847 (2011), See also FOCS 2008","DOI":"10.1137\/09075336X"},{"key":"86_CR14","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Time-space trade-offs for predecessor search. In: Proc. 38th ACM Symposium on Theory of Computing (STOC), pp. 232\u2013240 (2006)","DOI":"10.1145\/1132516.1132551"},{"key":"86_CR15","doi-asserted-by":"crossref","unstructured":"P\u01cetra\u015fcu, M., Thorup, M.: Higher lower bounds for near-neighbor and further rich problems. SIAM Journal on Computing\u00a039(2), 730\u2013741 (2010); See also FOCS 2006","DOI":"10.1137\/070684859"},{"key":"86_CR16","doi-asserted-by":"crossref","unstructured":"Sommer, C., Verbin, E., Yu, W.: Distance oracles for sparse graphs. In: Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 703\u2013712 (2009)","DOI":"10.1109\/FOCS.2009.27"},{"key":"86_CR17","unstructured":"Wang, Y., Yin, Y.: Certificates in data structures, \n                    \n                      http:\/\/arxiv.org\/abs\/1404.5743"},{"issue":"1","key":"86_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1867719.1867720","volume":"2","author":"Y. Yin","year":"2010","unstructured":"Yin, Y.: Cell-probe proofs. ACM Transactions on Computation Theory (TOCT)\u00a02(1), 1 (2010)","journal-title":"ACM Transactions on Computation Theory (TOCT)"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-43948-7_86","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T22:01:14Z","timestamp":1558908074000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-43948-7_86"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783662439470","9783662439487"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-43948-7_86","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}