{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T14:58:36Z","timestamp":1764687516514},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540734192"},{"type":"electronic","value":"9783540734208"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-73420-8_12","type":"book-chapter","created":{"date-parts":[[2007,8,25]],"date-time":"2007-08-25T10:58:43Z","timestamp":1188039523000},"page":"110-121","source":"Crossref","is-referenced-by-count":12,"title":["Unbounded-Error One-Way Classical and Quantum Communication Complexity"],"prefix":"10.1007","author":[{"given":"Kazuo","family":"Iwama","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rudy","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigeru","family":"Yamashita","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"12_CR1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.4086\/toc.2005.v001a001","volume":"1","author":"S. Aaronson","year":"2005","unstructured":"Aaronson, S.: Limitation of quantum advice and one-way communication. Theory of Computing\u00a01, 1\u201328 (2005)","journal-title":"Theory of Computing"},{"key":"12_CR2","unstructured":"Aaronson, S.: The learnability of quantum states, quant-ph\/0608142"},{"key":"12_CR3","doi-asserted-by":"publisher","first-page":"47","DOI":"10.4086\/toc.2005.v001a004","volume":"1","author":"S. Aaronson","year":"2005","unstructured":"Aaronson, S., Ambainis, A.: Quantum search of spatial regions. Theory of Computing\u00a01, 47\u201379 (2005)","journal-title":"Theory of Computing"},{"key":"12_CR4","unstructured":"Ambainis, A., Nayak, A., Ta-shma, A., Vazirani, U.: Dense quantum coding and a lower bound for 1-way quantum automata. In: Proc. 31st STOC, pp. 376\u2013383 (1999) Journal version appeared in J. ACM, 49, 496\u2013511 (2002)"},{"key":"12_CR5","doi-asserted-by":"crossref","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kerenidis, I.: Exponential separation of quantum and classical one-way communication complexity. In: Proc. 36th STOC, pp.\u00a0128\u2013137 (2004)","DOI":"10.1145\/1007352.1007379"},{"key":"12_CR6","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs. classical communication and computation. In: Proc. 30th STOC, pp.\u00a063\u201368 (1998)","DOI":"10.1145\/276698.276713"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, Article no 167902 (2001)","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"12_CR8","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1016\/S0022-0000(02)00019-3","volume":"65","author":"J. Forster","year":"2002","unstructured":"Forster, J.: A linear lower bound on the unbounded error probabilistic communication complexity. J. Comput. Syst. Sci.\u00a065, 612\u2013625 (2002)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1007\/3-540-45294-X_15","volume-title":"FST TCS 2001","author":"J. Forster","year":"2001","unstructured":"Forster, J., Krause, M., Lokam, S.V., Mubarakzjanov, R., Schmitt, N., Simon, H.U.: Relation between communication complexity, linear arrangements, and computational complexity. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FST TCS 2001. LNCS, vol.\u00a02245, pp. 171\u2013182. Springer, Heidelberg (2001)"},{"key":"12_CR10","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.tcs.2005.10.015","volume":"350","author":"J. Forster","year":"2006","unstructured":"Forster, J., Simon, H.U.: On the smallest possible dimension and the largest possible margin of linear arrangements representing given concept classes. Theoret. Comput. Sci.\u00a0350, 40\u201348 (2006)","journal-title":"Theoret. Comput. Sci."},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., de Wolf, R.: Exponential separations for one-way quantum communication complexity, with applications to cryptography. In: Proc. 39th STOC (to appear). Also, quant-ph\/06911209","DOI":"10.1145\/1250790.1250866"},{"key":"12_CR12","doi-asserted-by":"crossref","unstructured":"Gavinsky, D., Kempe, J., de Wolf, R.: Strengths and weaknesses of quantum fingerprinting. In: Proc. 21st CCC, pp.\u00a0288\u2013298 (2006)","DOI":"10.1109\/CCC.2006.39"},{"key":"12_CR13","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1088\/1367-2630\/8\/8\/129","volume":"8","author":"M. Hayashi","year":"2006","unstructured":"Hayashi, M., Iwama, K., Nishimura, H., Raymond, R., Yamashita, S. (4,1)-quantum random access coding does not exist \u2013 one qubit is not enough to recover one of four bits. New J. Phys. 8, Article no. 129 (2006)","journal-title":"New J. Phys."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1016\/S0375-9601(01)00455-8","volume":"286","author":"L. Jak\u00f3bczyk","year":"2001","unstructured":"Jak\u00f3bczyk, L., Siennicki, M.: Geometry of Bloch vectors in two-qubit system. Phys.\u00a0Lett.\u00a0A\u00a0286, 383\u2013390 (2001)","journal-title":"Phys.\u00a0Lett.\u00a0A"},{"key":"12_CR15","doi-asserted-by":"crossref","unstructured":"Klauck, H.: On quantum and probabilistic communication: Las Vegas and one-way protocols. In: Proc. 32nd STOC, pp.\u00a0644\u2013651 (2000)","DOI":"10.1145\/335305.335396"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Klauck, H.: Lower bounds for quantum communication complexity. In: Proc. 42nd FOCS, pp.\u00a0288\u2013297 (2001)","DOI":"10.1109\/SFCS.2001.959903"},{"key":"12_CR17","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s11080-005-0919-y","volume":"12","author":"G. Kimura","year":"2005","unstructured":"Kimura, G., Kossakowski, A.: The Bloch-vector space for N-level systems \u2013 the spherical-coordinate point of view. Open Sys. Information Dyn.\u00a012, 207\u2013229 (2005). Also, quant-ph\/0408014","journal-title":"Open Sys. Information Dyn."},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge (1997)","DOI":"10.1017\/CBO9780511574948"},{"key":"12_CR19","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/0020-0190(91)90157-D","volume":"39","author":"I. Newman","year":"1991","unstructured":"Newman, I.: Private vs. common random bits in communication complexity. Inform. Process. Lett.\u00a039, 67\u201371 (1991)","journal-title":"Inform. Process. Lett."},{"key":"12_CR20","doi-asserted-by":"crossref","unstructured":"Nayak, A.: Optimal lower bounds for quantum automata and random access codes. In: Proc. 40th IEEE FOCS, pp. 369\u2013376 (1999)","DOI":"10.1109\/SFFCS.1999.814608"},{"key":"12_CR21","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1145\/1120582.1120587","volume":"53","author":"A. Nayak","year":"2006","unstructured":"Nayak, A., Salzman, J.: Limits on the ability of quantum states to convey classical messages. J. ACM\u00a053, 184\u2013206 (2006)","journal-title":"J. ACM"},{"key":"12_CR22","unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information, Cambridge (2000)"},{"key":"12_CR23","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1016\/0022-0000(86)90046-2","volume":"33","author":"R. Paturi","year":"1986","unstructured":"Paturi, R., Simon, J.: Probabilistic communication complexity. J. Comput. Syst. Sci.\u00a033, 106\u2013123 (1986)","journal-title":"J. Comput. Syst. Sci."},{"key":"12_CR24","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1070\/IM2003v067n01ABEH000422","volume":"67","author":"A. Razborov","year":"2003","unstructured":"Razborov, A.: Quantum communication complexity of symmetric predicates. Izvestiya Mathematics\u00a067, 145\u2013159 (2003)","journal-title":"Izvestiya Mathematics"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-73420-8_12.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T06:10:57Z","timestamp":1619503857000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-73420-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540734192","9783540734208"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-73420-8_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}