{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:47:11Z","timestamp":1770752831698,"version":"3.50.0"},"publisher-location":"Berlin, Heidelberg","reference-count":35,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642315930","type":"print"},{"value":"9783642315947","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31594-7_52","type":"book-chapter","created":{"date-parts":[[2012,6,22]],"date-time":"2012-06-22T21:20:21Z","timestamp":1340400021000},"page":"617-628","source":"Crossref","is-referenced-by-count":9,"title":["Classical and Quantum Partition Bound and Detector Inefficiency"],"prefix":"10.1007","author":[{"given":"Sophie","family":"Laplante","sequence":"first","affiliation":[]},{"given":"Virginie","family":"Lerays","sequence":"additional","affiliation":[]},{"given":"J\u00e9r\u00e9mie","family":"Roland","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"52_CR1","doi-asserted-by":"crossref","unstructured":"Jain, R., Klauck, H.: The partition bound for classical complexity and query complexity. In: Proc. 25th CCC 2010, pp. 247\u2013258 (2010)","DOI":"10.1109\/CCC.2010.31"},{"key":"52_CR2","doi-asserted-by":"crossref","unstructured":"Newman, I., Szegedy, M.: Public vs. private coin flips in one round communication games. In: Proc. 28th STOC 1996, pp. 561\u2013570 (1996)","DOI":"10.1145\/237814.238004"},{"issue":"16","key":"52_CR3","doi-asserted-by":"publisher","first-page":"167902","DOI":"10.1103\/PhysRevLett.87.167902","volume":"87","author":"H. Buhrman","year":"2001","unstructured":"Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett.\u00a087(16), 167902 (2001)","journal-title":"Phys. Rev. Lett."},{"issue":"1","key":"52_CR4","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1137\/060651835","volume":"38","author":"Z. Bar-Yossef","year":"2008","unstructured":"Bar-Yossef, Z., Jayram, T.S., Kerenidis, I.: Exponential separation of quantum and classical one-way communication complexity. SIAM J. Comput.\u00a038(1), 366\u2013384 (2008)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"52_CR5","doi-asserted-by":"publisher","first-page":"1695","DOI":"10.1137\/070706550","volume":"38","author":"D. Gavinsky","year":"2008","unstructured":"Gavinsky, D., Kempe, J., Kerenidis, I., Raz, R., de Wolf, R.: Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput.\u00a038(5), 1695\u20131708 (2008)","journal-title":"SIAM J. Comput."},{"key":"52_CR6","doi-asserted-by":"crossref","unstructured":"Klartag, B., Regev, O.: Quantum one-way communication can be exponentially stronger than classical communication. In: Proc. 43rd STOC 2011, pp. 31\u201340 (2011)","DOI":"10.1145\/1993636.1993642"},{"key":"52_CR7","doi-asserted-by":"crossref","unstructured":"Yao, A.C.: Lower bounds by probabilistic arguments. In: Proc. 24th FOCS 1983, pp. 420\u2013428 (1983)","DOI":"10.1109\/SFCS.1983.30"},{"key":"52_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/3-540-45841-7_28","volume-title":"STACS 2002","author":"M. Graaf de","year":"2002","unstructured":"de Graaf, M., de Wolf, R.: On Quantum Versions of the Yao Principle. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 347\u2013358. Springer, Heidelberg (2002)"},{"key":"52_CR9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195","volume":"1","author":"J.S. Bell","year":"1964","unstructured":"Bell, J.S.: On the Einstein Podolsky Rosen paradox. Physics\u00a01, 195 (1964)","journal-title":"Physics"},{"issue":"7-8","key":"52_CR10","doi-asserted-by":"crossref","first-page":"649","DOI":"10.26421\/QIC11.7-8-8","volume":"11","author":"J. Degorre","year":"2011","unstructured":"Degorre, J., Kaplan, M., Laplante, S., Roland, J.: The communication complexity of non-signaling distributions. Quantum Information and Computation\u00a011(7-8), 649\u2013676 (2011)","journal-title":"Quantum Information and Computation"},{"key":"52_CR11","doi-asserted-by":"crossref","first-page":"032121","DOI":"10.1103\/PhysRevA.65.032121","volume":"65","author":"S. Massar","year":"2002","unstructured":"Massar, S.: Non locality, closing the detection loophole and communication complexity. Phys. Rev. A\u00a065, 032121 (2002)","journal-title":"Phys. Rev. A"},{"key":"52_CR12","doi-asserted-by":"crossref","first-page":"048301","DOI":"10.1103\/PhysRevLett.91.047903","volume":"91","author":"H. Buhrman","year":"2003","unstructured":"Buhrman, H., H\u00f8yer, P., Massar, S., R\u00f6hrig, H.: Combinatorics and quantum nonlocality. Phys. Rev. Lett.\u00a091, 048301 (2003)","journal-title":"Phys. Rev. Lett."},{"issue":"4","key":"52_CR13","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1561\/0400000040","volume":"3","author":"T. Lee","year":"2009","unstructured":"Lee, T., Shraibman, A.: Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science\u00a03(4), 263\u2013399 (2009)","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"issue":"3","key":"52_CR14","doi-asserted-by":"publisher","first-page":"368","DOI":"10.1002\/rsa.20232","volume":"34","author":"N. Linial","year":"2009","unstructured":"Linial, N., Shraibman, A.: Lower bounds in communication complexity based on factorization norms. Random Structures and Algorithms\u00a034(3), 368\u2013394 (2009)","journal-title":"Random Structures and Algorithms"},{"key":"52_CR15","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1016\/S0375-9601(99)00519-8","volume":"260","author":"B. Gisin","year":"1999","unstructured":"Gisin, B., Gisin, N.: A local hidden variable model of quantum correlation exploiting the detection loophole. Phys. Lett. A\u00a0260, 323\u2013327 (1999)","journal-title":"Phys. Lett. A"},{"key":"52_CR16","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Cleve, R., Wigderson, A.: Quantum vs classical communication and computation. In: Proc. 30th STOC 1998, pp. 63\u201368 (1998)","DOI":"10.1145\/276698.276713"},{"key":"52_CR17","doi-asserted-by":"publisher","first-page":"1874","DOI":"10.1103\/PhysRevLett.83.1874","volume":"83","author":"G. Brassard","year":"1999","unstructured":"Brassard, G., Cleve, R., Tapp, A.: Cost of exactly simulating quantum entanglement with classical communication. Phys. Rev. Lett.\u00a083, 1874\u20131877 (1999)","journal-title":"Phys. Rev. Lett."},{"key":"52_CR18","doi-asserted-by":"publisher","first-page":"12321","DOI":"10.1103\/PhysRevA.73.012321","volume":"73","author":"H. Buhrman","year":"2006","unstructured":"Buhrman, H., H\u00f8yer, P., Massar, S., R\u00f6hrig, H.: Multipartite nonlocal quantum correlations resistant to imperfections. Phys. Rev. A\u00a073, 012321 (2006)","journal-title":"Phys. Rev. A"},{"key":"52_CR19","doi-asserted-by":"crossref","unstructured":"Buhrman, H., Regev, O., Scarpa, G., de Wolf, R.: Near-optimal and explicit Bell inequality violations. In: Proc. 26th CCC 2011, pp. 157\u2013166 (2011)","DOI":"10.1109\/CCC.2011.30"},{"key":"52_CR20","unstructured":"Lov\u00e1sz, L.: Communication Complexity: a Survey. In: Paths, Flows, and VLSI Layout, B.H. Korte edition. Springer (1990)"},{"issue":"1","key":"52_CR21","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1137\/S0895480192238482","volume":"8","author":"M. Karchmer","year":"1995","unstructured":"Karchmer, M., Kushilevitz, E., Nisan, N.: Fractional covers and communication complexity. SIAM J. Discrete Math.\u00a08(1), 76\u201392 (1995)","journal-title":"SIAM J. Discrete Math."},{"key":"52_CR22","doi-asserted-by":"crossref","unstructured":"Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. In: Proc. 26th FOCS 1985, pp. 429\u2013442 (1985)","DOI":"10.1109\/SFCS.1985.62"},{"key":"52_CR23","doi-asserted-by":"crossref","unstructured":"Babai, L., Nisan, N., Szegedy, M.: Multiparty protocols and logspace-hard pseudorandom sequences. In: Proc. 21st STOC 1989, pp. 1\u201311 (1989)","DOI":"10.1145\/73007.73008"},{"issue":"2","key":"52_CR24","doi-asserted-by":"publisher","first-page":"61","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. Information Processing Letters\u00a039(2), 61\u201371 (1991)","journal-title":"Information Processing Letters"},{"key":"52_CR25","doi-asserted-by":"crossref","unstructured":"Khot, S., Vishnoi, N.: The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l 1. In: Proc. 46th FOCS 2005, pp. 53\u201362 (2005)","DOI":"10.1145\/2629614"},{"key":"52_CR26","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":"52_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/3-540-45841-7_24","volume-title":"STACS 2002","author":"P. H\u00f8yer","year":"2002","unstructured":"H\u00f8yer, P., de Wolf, R.: Improved Quantum Communication Complexity Bounds for Disjointness and Equality. In: Alt, H., Ferreira, A. (eds.) STACS 2002. LNCS, vol.\u00a02285, pp. 299\u2013310. Springer, Heidelberg (2002)"},{"key":"52_CR28","doi-asserted-by":"crossref","unstructured":"Jain, R., Klauck, H., Nayak, A.: Direct product theorems for communication complexity via subdistribution bounds. In: Proc. 40th STOC 2008, pp. 599\u2013608 (2008)","DOI":"10.1145\/1374376.1374462"},{"key":"52_CR29","doi-asserted-by":"publisher","first-page":"210503","DOI":"10.1103\/PhysRevLett.100.210503","volume":"100","author":"N. Brunner","year":"2008","unstructured":"Brunner, N., Pironio, S., Ac\u00edn, A., Gisin, N., M\u00e9thot, A., Scarani, V.: Testing the dimension of Hilbert spaces. Phys. Rev. Lett.\u00a0100, 210503 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"52_CR30","doi-asserted-by":"crossref","first-page":"060401","DOI":"10.1103\/PhysRevLett.104.060401","volume":"104","author":"T. V\u00e9rtesi","year":"2010","unstructured":"V\u00e9rtesi, T., Pironio, S., Brunner, N.: Closing the detection loophole in Bell experiments using qudits. Phys. Rev. Lett.\u00a0104, 060401 (2010)","journal-title":"Phys. Rev. Lett."},{"key":"52_CR31","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Shi, Y., Wirth, A., Yao, A.: Informational complexity and the direct sum problem for simultaneous message complexity. In: Proc. 42nd FOCS 2001, pp. 270\u2013278 (2001)","DOI":"10.1109\/SFCS.2001.959901"},{"key":"52_CR32","unstructured":"Braverman, M., Weinstein, O.: A discrepancy lower bound for information complexity. Technical Report 12-164, ECCC (2011)"},{"key":"52_CR33","doi-asserted-by":"crossref","unstructured":"Kerenidis, I., Laplante, S., Lerays, V., Roland, J., Xiao, D.: Lower bounds on information complexity via zero-communication protocols and applications. Technical Report 12-038, ECCC (2012)","DOI":"10.1109\/FOCS.2012.68"},{"issue":"7","key":"52_CR34","doi-asserted-by":"crossref","first-page":"073013","DOI":"10.1088\/1367-2630\/10\/7\/073013","volume":"10","author":"M. Navascu\u00e9s","year":"2008","unstructured":"Navascu\u00e9s, M., Pironio, S., Ac\u00edn, A.: A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics\u00a010(7), 073013 (2008)","journal-title":"New Journal of Physics"},{"key":"52_CR35","doi-asserted-by":"crossref","unstructured":"Doherty, A.C., Liang, Y.-C., Toner, B., Wehner, S.: The quantum moment problem and bounds on entangled multi-prover games. In: Proc. 23rd CCC 2008, pp. 199\u2013210 (2008)","DOI":"10.1109\/CCC.2008.26"}],"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-642-31594-7_52.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T12:10:52Z","timestamp":1743595852000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31594-7_52"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642315930","9783642315947"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31594-7_52","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}