{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,22]],"date-time":"2025-01-22T05:26:20Z","timestamp":1737523580141,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540422877"},{"type":"electronic","value":"9783540482246"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-48224-5_30","type":"book-chapter","created":{"date-parts":[[2007,10,28]],"date-time":"2007-10-28T06:29:04Z","timestamp":1193552944000},"page":"358-369","source":"Crossref","is-referenced-by-count":4,"title":["Lower Bounds in the Quantum Cell Probe Model"],"prefix":"10.1007","author":[{"given":"Pranab","family":"Sen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Venkatesh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,4]]},"reference":[{"key":"30_CR1","doi-asserted-by":"crossref","unstructured":"P. Beame and F. Fich. Optimal bounds for the predecessor problem. In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, pages 295\u2013304, 1999.","DOI":"10.1145\/301250.301323"},{"key":"30_CR2","doi-asserted-by":"crossref","unstructured":"H. Buhrman, P. Miltersen, J. Radhakrishnan, and S. Venkatesh. Are bitvectors Optimal? In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 449\u2013458, 2000.","DOI":"10.1145\/335305.335357"},{"key":"30_CR3","series-title":"Lect Notes Comput Sci","first-page":"61","volume-title":"Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications","author":"R. Cleve","year":"1998","unstructured":"R. Cleve, W. van Dam,, M. Nielsen, and A. Tapp. Quantum entanglement and the communication complexity of the inner product function. In Proceedings of the 1st NASA International Conference on Quantum Computing and Quantum Communications, Lecture Notes in Computer Science, vol. 1509, pages 61\u201374, 1998. Also quant-ph\/9708019."},{"issue":"3","key":"30_CR4","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"M. Fredman","year":"1984","unstructured":"M. Fredman, J. Koml\u00f3s, and E. Szemer\u00e9di. Storing a sparse table with O(1) worst case access time. Journal of the Association for Computing Machinery, 31(3):538\u2013544, 1984.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"L. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the 28th Annual ACM Symposium on Theory of Computing, pages 212\u2013219, 1996. Also quant-ph\/9605043.","DOI":"10.1145\/237814.237866"},{"key":"30_CR6","unstructured":"P. H\u00f8yer and J. Neerbek. Bounds on quantum ordered searching. Manuscript at quant-ph\/0009032, September 2000."},{"key":"30_CR7","unstructured":"H. Klauck. On rounds in quantum communication. Manuscript at quant-ph\/0004100, April 2000."},{"key":"30_CR8","unstructured":"P. B. Miltersen. Cell probe complexity \u2014 a survey. Invited talk at the pre-conference workshop on Advances in data structures preceding the 19th conference on the Foundations of Software Technology and Theoretical Computer Science, December 11-12, 1999, Chennai, India. Also available from http:\/\/www.daimi.au.dk\/~bromille\/Papers\/survey3.ps ."},{"key":"30_CR9","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P. B. Miltersen","year":"1998","unstructured":"P. B. Miltersen, N. Nisan, S. Safra, and A. Wigderson. On data structures and asymmetric communication complexity. Journal of Computer and System Sciences, 57:37\u201349, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"30_CR10","unstructured":"A. Nayak, A. Ta-Shma, and D. Zuckerman. Interaction in quantum communication complexity. Manuscript at quant-ph\/0005106, May 2000."},{"key":"30_CR11","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"I. Newman. Private vs common random bits in communication complexity. Information Processing Letters, 39:67\u201371, 1991.","journal-title":"Information Processing Letters"},{"key":"30_CR12","unstructured":"M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000."},{"key":"30_CR13","doi-asserted-by":"crossref","unstructured":"J. Radhakrishnan, P. Sen, and S. Venkatesh. The quantum complexity of set membership. In Proceedings of the 41st Annual IEEE Symposium on Foundations of Computer Science, pages 554\u2013562, 2000. Also quant-ph\/0007021.","DOI":"10.1109\/SFCS.2000.892143"},{"key":"30_CR14","unstructured":"P. Sen and S. Venkatesh. Lower bounds in the quantum cell probe model. Full version. Manuscript at quant-ph\/0104100."},{"key":"30_CR15","doi-asserted-by":"crossref","unstructured":"A. C-C. Yao. Probabilistic computations: towards a unified measure of complexity. In Proceedings of the 9th Annual ACM Symposium on Theory of Computing, pages 209\u2013213, 1977.","DOI":"10.1109\/SFCS.1977.24"},{"issue":"3","key":"30_CR16","doi-asserted-by":"crossref","first-page":"615","DOI":"10.1145\/322261.322274","volume":"28","author":"A. C.-C. Yao","year":"1981","unstructured":"A. C-C. Yao. Should tables be sorted? Journal of the Association for Computing Machinery, 28(3):615\u2013628, 1981.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"30_CR17","unstructured":"A. C-C. Yao. Quantum circuit complexity. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 352\u2013361, 1993."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-48224-5_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T23:50:33Z","timestamp":1737503433000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-48224-5_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540422877","9783540482246"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-48224-5_30","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}