{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,7]],"date-time":"2025-08-07T21:23:01Z","timestamp":1754601781208},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540002253"},{"type":"electronic","value":"9783540362067"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-36206-1_20","type":"book-chapter","created":{"date-parts":[[2007,8,16]],"date-time":"2007-08-16T03:23:08Z","timestamp":1187234588000},"page":"218-229","source":"Crossref","is-referenced-by-count":7,"title":["The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version"],"prefix":"10.1007","author":[{"given":"Rahul","family":"Jain","sequence":"first","affiliation":[]},{"given":"Jaikumar","family":"Radhakrishnan","sequence":"additional","affiliation":[]},{"given":"Pranab","family":"Sen","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,12,16]]},"reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"D. Aharonov, A. Kitaev, and N. Nisan. Quantum circuits with mixed states. In Proceedings of the 30th Annual ACM Symposium on Theory of Computing, pages 20\u201330, 1998. Also quant-ph\/9806029.","DOI":"10.1145\/276698.276708"},{"key":"20_CR2","doi-asserted-by":"crossref","unstructured":"A. Ambainis, L. Schulman, A. Ta-Shma, U. Vazirani, and A. Wigderson. The quantum communication complexity of sampling. In Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, pages 342\u2013351, 1998.","DOI":"10.1109\/SFCS.1998.743480"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"T. Cover and J. Thomas. Elements of Information Theory. Wiley Series in Telecommunications. John Wiley and Sons, 1991.","DOI":"10.1002\/0471200611"},{"key":"20_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/0890-5401(87)90037-X","volume":"73","author":"P. Duris","year":"1987","unstructured":"P. Duris, Z. Galil, and G. Schnitger. Lower bounds on communication complexity. Information and Computation, 73:1\u201322, 1987.","journal-title":"Information and Computation"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"R. Jain, J. Radhakrishnan, and P. Sen. Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. To appear.","DOI":"10.1109\/SFCS.2002.1181967"},{"key":"20_CR6","doi-asserted-by":"crossref","unstructured":"H. Klauck. On quantum and probabilistic communication: Las Vegas and oneway protocols. In Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, pages 644\u2013651, 2000.","DOI":"10.1145\/335305.335396"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"H. Klauck, A. Nayak, A. Ta-Shma, and D. Zuckerman. Interaction in quantum communication and the complexity of set disjointness. In Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, pages 124\u2013133, 2001.","DOI":"10.1145\/380752.380786"},{"issue":"1","key":"20_CR8","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(1):37\u201349, 1998.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR9","unstructured":"M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000."},{"key":"20_CR10","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1137\/0222016","volume":"22","author":"N. Nisan","year":"1993","unstructured":"N. Nisan and A. Wigderson. Rounds in communication complexity revisited. SIAM Journal of Computing, 22:211\u2013219, 1993.","journal-title":"SIAM Journal of Computing"},{"key":"20_CR11","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1016\/0022-0000(84)90069-2","volume":"28","author":"C. Papadimitriou","year":"1984","unstructured":"C. Papadimitriou and M. Sipser. Communication complexity. Journal of Computer and System Sciences, 28:260\u2013269, 1984.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"20_CR12","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1006\/jcss.2000.1731","volume":"62","author":"S. Ponzio","year":"2001","unstructured":"S. Ponzio, J. Radhakrishnan, and S. Venkatesh. The communication complexity of pointer chasing. Journal of Computer and System Sciences, 62(2):323\u2013355, 2001.","journal-title":"Journal of Computer and System Sciences"},{"key":"20_CR13","unstructured":"A. Razborov. Quantum communication complexity of symmetric predicates. Manuscript at quant-ph\/0204025, April 2002."},{"key":"20_CR14","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1007\/3-540-48224-5_30","volume-title":"Proceedings of the 28th International Colloquium on Automata, Languages and Programming","author":"P. Sen","year":"2001","unstructured":"P. Sen and S. Venkatesh. Lower bounds in the quantum cell probe model. In Proceedings of the 28th International Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, vol. 2076, pages 358\u2013369. Springer-Verlag, 2001. Also quant-ph\/0104100."},{"key":"20_CR15","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","FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-36206-1_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T00:07:46Z","timestamp":1556755666000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-36206-1_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540002253","9783540362067"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-36206-1_20","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}