{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T15:12:11Z","timestamp":1784301131567,"version":"3.55.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T00:00:00Z","timestamp":1405382400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,7,15]]},"DOI":"10.1145\/2611462.2611488","type":"proceedings-article","created":{"date-parts":[[2014,7,15]],"date-time":"2014-07-15T12:20:56Z","timestamp":1405426856000},"page":"166-175","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Can quantum communication speed up distributed computation?"],"prefix":"10.1145","author":[{"given":"Michael","family":"Elkin","sequence":"first","affiliation":[{"name":"Department of Computer Science, Ben-Gurion University, Be'er Sheva, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hartmut","family":"Klauck","sequence":"additional","affiliation":[{"name":"Nanyang Technological University & Centre for Quantum Technologies, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danupon","family":"Nanongkai","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of Vienna, Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"Nanyang Technological University & Brown University, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2014,7,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946329"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.006"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysicsPhysiqueFizika.1.195"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060662"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412717"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45138-9_1"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.60.2737"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611491"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/1888781.1888814"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.56.1201"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_14_1","volume-title":"Distributed computation of sparse cuts. CoRR, abs\/1310.5407","author":"Sarma A. Das","year":"2013","unstructured":"A. Das Sarma , A. R. Molla , and G. Pandurangan . Distributed computation of sparse cuts. CoRR, abs\/1310.5407 , 2013 . A. Das Sarma, A. R. Molla, and G. Pandurangan. Distributed computation of sparse cuts. CoRR, abs\/1310.5407, 2013."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432624"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00377-8"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1412700.1412718"},{"key":"e_1_3_2_1_18_1","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"Dubhashi D. P.","year":"2007","unstructured":"D. P. Dubhashi , F. Grandioni , and A. Panconesi . Distributed Algorithms via LP Duality and Randomization . In Handbook of Approximation Algorithms and Metaheuristics . Chapman and Hall\/CRC , 2007 . D. P. Dubhashi, F. Grandioni, and A. Panconesi. Distributed Algorithms via LP Duality and Randomization. In Handbook of Approximation Algorithms and Metaheuristics. Chapman and Hall\/CRC, 2007."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRev.47.777"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1054916.1054931"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441058"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/2095116.2095207"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.100.070504"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261118"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1813164.1813197"},{"key":"e_1_3_2_1_26_1","volume-title":"ICALP (2)","author":"Ghaffari M.","year":"2014","unstructured":"M. Ghaffari . Near-optimal distributed approximation of minimum-weight connected dominating set . In ICALP (2) , 2014 . M. Ghaffari. Near-optimal distributed approximation of minimum-weight connected dominating set. In ICALP (2), 2014."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41527-2_1"},{"issue":"3","key":"e_1_3_2_1_28_1","first-page":"3","article-title":"Bounds for the quantity of information transmitted by a quantum communication channel","volume":"9","author":"Holevo A. S.","year":"1973","unstructured":"A. S. Holevo . Bounds for the quantity of information transmitted by a quantum communication channel . Problemy Peredachi Informatsii , 9 ( 3 ): 3 -- 11 , 1973 . English translation in Problems of Information Transmission, 9:177--183, 1973. A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9(3):3--11, 1973. English translation in Problems of Information Transmission, 9:177--183, 1973.","journal-title":"Problemy Peredachi Informatsii"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2332432.2332504"},{"key":"e_1_3_2_1_30_1","first-page":"148","volume-title":"FSTTCS","author":"Ivanyos G.","year":"2012","unstructured":"G. Ivanyos , H. Klauck , T. Lee , M. Santha , and R. de Wolf . New bounds on the classical and quantum communication complexity of some graph properties . In FSTTCS , pages 148 -- 159 , 2012 . G. Ivanyos, H. Klauck, T. Lee, M. Santha, and R. de Wolf. New bounds on the classical and quantum communication complexity of some graph properties. In FSTTCS, pages 148--159, 2012."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400751.1400787"},{"key":"e_1_3_2_1_33_1","volume-title":"Manuscript","author":"Klauck H.","year":"2012","unstructured":"H. Klauck and R. de Wolf . Fooling one-sided quantum protocols . Manuscript , 2012 . H. Klauck and R. de Wolf. Fooling one-sided quantum protocols. Manuscript, 2012."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1582716.1582796"},{"key":"e_1_3_2_1_35_1","volume-title":"Computing on anonymous quantum network. CoRR, abs\/1001.5307","author":"Kobayashi H.","year":"2010","unstructured":"H. Kobayashi , K. Matsumoto , and S. Tani . Computing on anonymous quantum network. CoRR, abs\/1001.5307 , 2010 . H. Kobayashi, K. Matsumoto, and S. Tani. Computing on anonymous quantum network. CoRR, abs\/1001.5307, 2010."},{"key":"e_1_3_2_1_36_1","first-page":"69","volume-title":"STACS","author":"Kor L.","year":"2011","unstructured":"L. Kor , A. Korman , and D. Peleg . Tight bounds for distributed mst verification . In STACS , pages 69 -- 80 , 2011 . L. Kor, A. Korman, and D. Peleg. Tight bounds for distributed mst verification. In STACS, pages 69--80, 2011."},{"key":"e_1_3_2_1_37_1","volume-title":"Communication complexity","author":"Kushilevitz E.","year":"1997","unstructured":"E. Kushilevitz and N. Nisan . Communication complexity . Cambridge University Press , New York, NY, USA , 1997 . E. Kushilevitz and N. Nisan. Communication complexity. Cambridge University Press, New York, NY, USA, 1997."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/1803907"},{"key":"e_1_3_2_1_40_1","first-page":"475","volume-title":"ICALP (1)","author":"Lee T.","year":"2010","unstructured":"T. Lee and S. Zhang . Composition theorems in communication complexity . In ICALP (1) , pages 475 -- 489 , 2010 . T. Lee and S. Zhang. Composition theorems in communication complexity. In ICALP (1), pages 475--489, 2010."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488656"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v34:3"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/383962.383984"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611511"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591850"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993853"},{"key":"e_1_3_2_1_49_1","volume-title":"Manuscript","author":"Nanongkai D.","year":"2014","unstructured":"D. Nanongkai and H. Su . Almost-tight distributed minimum cut algorithms . Manuscript , 2014 . D. Nanongkai and H. Su. Almost-tight distributed minimum cut algorithms. Manuscript, 2014."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796491"},{"key":"e_1_3_2_1_51_1","volume-title":"Quantum Computation and Quantum Information","author":"Nielsen M. A.","year":"2004","unstructured":"M. A. Nielsen and I. L. Chuang . Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences). Cambridge University Press , 1 edition, Jan. 2004 . M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information (Cambridge Series on Information and the Natural Sciences). Cambridge University Press, 1 edition, Jan. 2004."},{"key":"e_1_3_2_1_52_1","volume-title":"Multi-partite quantum entanglement versus randomization: Fair and unbiased leader election in networks","author":"Pal S. P.","year":"2003","unstructured":"S. P. Pal , S. K. Singh , and S. Kumar . Multi-partite quantum entanglement versus randomization: Fair and unbiased leader election in networks , 2003 . S. P. Pal, S. K. Singh, and S. Kumar. Multi-partite quantum entanglement versus randomization: Fair and unbiased leader election in networks, 2003."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/355459"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301343"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366870"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"issue":"1","key":"e_1_3_2_1_58_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestiya","volume":"67","author":"Razborov A. A.","year":"2003","unstructured":"A. A. Razborov . Quantum communication complexity of symmetric predicates. Izvestiya : Mathematics , 67 ( 1 ): 145 , 2003 . A. A. Razborov. Quantum communication complexity of symmetric predicates. Izvestiya: Mathematics, 67(1):145, 2003.","journal-title":"Mathematics"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733644"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2612669.2612706"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431223"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/333623.333628"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31856-9_48"}],"event":{"name":"PODC '14: ACM Symposium on Principles of Distributed Computing","location":"Paris France","acronym":"PODC '14","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2014 ACM symposium on Principles of distributed computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611462.2611488","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2611462.2611488","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:56:05Z","timestamp":1750229765000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2611462.2611488"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,15]]},"references-count":63,"alternative-id":["10.1145\/2611462.2611488","10.1145\/2611462"],"URL":"https:\/\/doi.org\/10.1145\/2611462.2611488","relation":{},"subject":[],"published":{"date-parts":[[2014,7,15]]},"assertion":[{"value":"2014-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}