{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,23]],"date-time":"2025-07-23T12:46:10Z","timestamp":1753274770873,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540771180"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-77120-3_11","type":"book-chapter","created":{"date-parts":[[2007,12,6]],"date-time":"2007-12-06T11:31:09Z","timestamp":1196940669000},"page":"100-111","source":"Crossref","is-referenced-by-count":5,"title":["Unbounded-Error 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":[{"doi-asserted-by":"crossref","unstructured":"Alon, N., Frankl, P., R\u00f6dl, V.: Geometrical realization of set systems and probabilistic communication complexity. In: Proc. 26th FOCS, pp. 277\u2013280 (1985)","key":"11_CR1","DOI":"10.1109\/SFCS.1985.30"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1145\/581771.581773","volume":"49","author":"A. Ambainis","year":"2002","unstructured":"Ambainis, A., Nayak, A., Ta-shma, A., Vazirani, U.: Dense quantum coding and quantum finite automata. J. ACM\u00a049, 496\u2013511 (2002)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Babai, L., Frankl, P., Simon, J.: Complexity classes in communication complexity. In: Proc. 27th FOCS, pp.\u00a0303\u2013312 (1986)","key":"11_CR3","DOI":"10.1109\/SFCS.1986.15"},{"doi-asserted-by":"crossref","unstructured":"Babai, L., Kimmel, P.: Randomized simultaneous messages: solution of a problem of Yao in communication complexity. In: Proc. 12th CCC, pp. 239\u2013246 (1997)","key":"11_CR4","DOI":"10.1109\/CCC.1997.612319"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett.\u00a087 Article no.\u00a0167902 (2001)","key":"11_CR5","DOI":"10.1103\/PhysRevLett.87.167902"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., Vereshchagin, N., de Wolf, R.: On computation and communication with small bias. In: Proc. 22nd CCC, pp.\u00a024\u201332 (2007)","key":"11_CR6","DOI":"10.1109\/CCC.2007.18"},{"doi-asserted-by":"crossref","unstructured":"Buhrman, H., de Wolf, R.: Communication Complexity Lower Bounds by Polynomials. In: Proc. 16th CCC, pp.\u00a0120\u2013130, Also, cs.CC\/9910010 (2001)","key":"11_CR7","DOI":"10.1109\/CCC.2001.933879"},{"key":"11_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":"11_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: Foundations of Software Technology and Theoretical Computer Science","author":"J. Forster","year":"2001","unstructured":"Forster, J., Krause, M., Lokam, S.V., Mubarakzjanov, R., Schmitt, N., Simon, H.U.: Relations between communication complexity, linear arrangements, and computational complexity. In: Hariharan, R., Mukund, M., Vinay, V. (eds.) FST TCS 2001: Foundations of Software Technology and Theoretical Computer Science. LNCS, vol.\u00a02245, pp. 171\u2013182. Springer, Heidelberg (2001)"},{"key":"11_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."},{"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, pp.\u00a0516\u2013525, Also, quant-ph\/0611209 (2007)","key":"11_CR11","DOI":"10.1145\/1250790.1250866"},{"doi-asserted-by":"crossref","unstructured":"Gavinsky, D., Kempe, J., Regev, O., de Wolf, R.: Bounded-error quantum state identification and exponential separations in communication complexity. In: Proc. 38th STOC, pp.\u00a0594\u2013603 (2006)","key":"11_CR12","DOI":"10.1145\/1132516.1132602"},{"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)","key":"11_CR13","DOI":"10.1109\/CCC.2006.39"},{"key":"11_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1007\/978-3-540-73420-8_12","volume-title":"ICALP 2007","author":"K. Iwama","year":"2007","unstructured":"Iwama, K., Nishimura, H., Raymond, R., Yamashita, S.: Unbounded-error one-way classical and quantum communication complexity. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 110\u2013121. Springer, Heidelberg (2007) Also, quant-ph\/0706.3265"},{"key":"11_CR15","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":"11_CR16","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)","journal-title":"Open Sys. Information Dyn."},{"key":"11_CR17","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0097539702405620","volume":"37","author":"H. Klauck","year":"2007","unstructured":"Klauck, H.: Lower bounds for quantum communication complexity. SIAM J. Comput.\u00a037, 20\u201346 (2007)","journal-title":"SIAM J. Comput."},{"key":"11_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-540-24587-2_21","volume-title":"Algorithms and Computation","author":"H. Kobayashi","year":"2003","unstructured":"Kobayashi, H., Matsumoto, K., Yamakami, T.: Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur? In: Ibaraki, T., Katoh, N., Ono, H. (eds.) ISAAC 2003. LNCS, vol.\u00a02906, pp. 189\u2013198. Springer, Heidelberg (2003)"},{"key":"11_CR19","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1023\/A:1025101606680","volume":"10","author":"A. Kossakowski","year":"2003","unstructured":"Kossakowski, A.: A class of linear positive maps in matrix algebras. Open Sys. Information Dyn.\u00a010, 213\u2013220 (2003)","journal-title":"Open Sys. Information Dyn."},{"unstructured":"Kremer, I.: Quantum Communication. Master\u2019s Thesis, The Hebrew Univ. of Jerusalem (1995)","key":"11_CR20"},{"doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge (1997)","key":"11_CR21","DOI":"10.1017\/CBO9780511574948"},{"unstructured":"Linial, N., Shraibman, A.: Learning complexity vs. communication complexity (2006), Manuscript Available at http:\/\/www.cs.huji.ac.il\/~nati\/","key":"11_CR22"},{"doi-asserted-by":"crossref","unstructured":"Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. In: Proc. 39th STOC, pp. 699\u2013708 (2007)","key":"11_CR23","DOI":"10.1145\/1250790.1250892"},{"doi-asserted-by":"crossref","unstructured":"Newman, I., Szegedy, M.: Public vs. private coin flips in one-round communication games. In: Proc. 28th STOC, pp.\u00a0561\u2013570 (1996)","key":"11_CR24","DOI":"10.1145\/237814.238004"},{"unstructured":"Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge (2000)","key":"11_CR25"},{"key":"11_CR26","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) Preliminary version appeared in Proc. 25th FOCS, pp.\u00a0118\u2013126 (1984)","journal-title":"J. Comput. Syst. Sci."},{"doi-asserted-by":"crossref","unstructured":"Raz, R.: Exponential separation of quantum and classical communication complexity. In: Proc. 31st STOC, pp. 358\u2013367 (1999)","key":"11_CR27","DOI":"10.1145\/301250.301343"},{"doi-asserted-by":"crossref","unstructured":"Sherstov, A.: Halfspace matrices. In: Proc. 22nd CCC, pp.\u00a083\u201395 (2007)","key":"11_CR28","DOI":"10.1109\/CCC.2007.11"},{"key":"11_CR29","doi-asserted-by":"publisher","first-page":"681","DOI":"10.1137\/S0097539702407345","volume":"32","author":"R. Wolf de","year":"2003","unstructured":"de Wolf, R.: Nondeterministic quantum query and communication complexities. SIAM J. Comput.\u00a032, 681\u2013699 (2003)","journal-title":"SIAM J. Comput."},{"unstructured":"Yao, A.C.-C.: Quantum circuit complexity. In: Proc. 34th FOCS, pp.\u00a0352\u2013360 (1993)","key":"11_CR30"},{"doi-asserted-by":"crossref","unstructured":"Yao, A.C.-C.: On the power of quantum fingerprinting. In: Proc. 35th STOC, pp.\u00a077\u201381 (2003)","key":"11_CR31","DOI":"10.1145\/780542.780554"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-77120-3_11.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,23]],"date-time":"2025-01-23T08:10:32Z","timestamp":1737619832000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-77120-3_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540771180"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-77120-3_11","relation":{},"subject":[]}}