{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:24:01Z","timestamp":1787509441227,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":17,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384243","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"401-411","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Bare Quantum simultaneity versus classical interactivity in communication complexity"],"prefix":"10.1145","author":[{"given":"Dmitry","family":"Gavinsky","sequence":"first","affiliation":[{"name":"Czech Academy of Sciences, Czechia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"D. Angluin and L. Valiant. 1979. Fast Probabilistic Algorithms for Hamiltonian Paths and Matchings. Journal of Computer and System Sciences 18 ( 1979 ) 155-193.  D. Angluin and L. Valiant. 1979. Fast Probabilistic Algorithms for Hamiltonian Paths and Matchings. Journal of Computer and System Sciences 18 ( 1979 ) 155-193.","DOI":"10.1016\/0022-0000(79)90045-X"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of 36th Symposium on Theory of Computing ( 2004 ), 128-137","author":"Bar-Yossef Z.","unstructured":"Z. Bar-Yossef , T. S. Jayram , and I. Kerenidis . 2004. Exponential Separation of Quantum and Classical One-Way Communication Complexity . Proceedings of 36th Symposium on Theory of Computing ( 2004 ), 128-137 . Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. 2004. Exponential Separation of Quantum and Classical One-Way Communication Complexity. Proceedings of 36th Symposium on Theory of Computing ( 2004 ), 128-137."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"crossref","unstructured":"H. Buhrman R. Cleve S. Massar and R. de Wolf. 2010. Nonlocality and Communication Complexity. Reviews of Modern Physics 82 ( 1 ) ( 2010 ) 665-698.  H. Buhrman R. Cleve S. Massar and R. de Wolf. 2010. Nonlocality and Communication Complexity. Reviews of Modern Physics 82 ( 1 ) ( 2010 ) 665-698.","DOI":"10.1103\/RevModPhys.82.665"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"H. Buhrman R. Cleve J. Watrous and R. de Wolf. 2001. Quantum Fingerprinting. Physical Review Letters 87 ( 16 ) article 167902 ( 2001 ).  H. Buhrman R. Cleve J. Watrous and R. de Wolf. 2001. Quantum Fingerprinting. Physical Review Letters 87 ( 16 ) article 167902 ( 2001 ).","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"e_1_3_2_1_5_1","volume-title":"Proceedings of the 30th Symposium on Theory of Computing ( 1998 ), 63-68","author":"Buhrman H.","unstructured":"H. Buhrman , R. Cleve , and A. Wigderson . 1998. Quantum vs. Classical Communication and Computation . Proceedings of the 30th Symposium on Theory of Computing ( 1998 ), 63-68 . H. Buhrman, R. Cleve, and A. Wigderson. 1998. Quantum vs. Classical Communication and Computation. Proceedings of the 30th Symposium on Theory of Computing ( 1998 ), 63-68."},{"key":"e_1_3_2_1_6_1","volume-title":"Proceedings of the 43rd Symposium on Theory of Computing ( 2011 ), 51-60","author":"Chakrabarti A.","unstructured":"A. Chakrabarti and O. Regev . 2011. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance . Proceedings of the 43rd Symposium on Theory of Computing ( 2011 ), 51-60 . A. Chakrabarti and O. Regev. 2011. An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance. Proceedings of the 43rd Symposium on Theory of Computing ( 2011 ), 51-60."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374393"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2918453"},{"key":"e_1_3_2_1_9_1","volume-title":"Entangled Simultaneity Versus Classical Interactivity in Communication Complexity","author":"Gavinsky D.","unstructured":"D. Gavinsky . 2020. Entangled Simultaneity Versus Classical Interactivity in Communication Complexity . IEEE Transactions on Information Theory to appear ( 2020 ). D. Gavinsky. 2020. Entangled Simultaneity Versus Classical Interactivity in Communication Complexity. IEEE Transactions on Information Theory to appear ( 2020 )."},{"key":"e_1_3_2_1_10_1","series-title":"SIAM Journal on Computing 38 ( 5 ) ( 2008 ), 1695-1708","volume-title":"Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography","author":"Gavinsky D.","unstructured":"D. Gavinsky , J. Kempe , I. Kerenidis , R. Raz , and R. de Wolf . 2008. Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography . SIAM Journal on Computing 38 ( 5 ) ( 2008 ), 1695-1708 . D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. 2008. Exponential Separations for One-Way Quantum Communication Complexity, with Applications to Cryptography. SIAM Journal on Computing 38 ( 5 ) ( 2008 ), 1695-1708."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 44th Annual Symposium on Foundations of Computer Science ( 2003 ), 283-289","author":"Indyk P.","unstructured":"P. Indyk and D. Woodruf . 2003. Tight Lower Bounds for the Distinct Elements Problem . Proceedings of the 44th Annual Symposium on Foundations of Computer Science ( 2003 ), 283-289 . P. Indyk and D. Woodruf. 2003. Tight Lower Bounds for the Distinct Elements Problem. Proceedings of the 44th Annual Symposium on Foundations of Computer Science ( 2003 ), 283-289."},{"key":"e_1_3_2_1_12_1","volume-title":"Proceedings of the 43st Symposium on Theory of Computing ( 2011 ), 31-40","author":"Klartag B.","unstructured":"B. Klartag and O. Regev . 2011. Quantum One-Way Communication Can Be Exponentially Stronger than Classical Communication . Proceedings of the 43st Symposium on Theory of Computing ( 2011 ), 31-40 . B. Klartag and O. Regev. 2011. Quantum One-Way Communication Can Be Exponentially Stronger than Classical Communication. Proceedings of the 43st Symposium on Theory of Computing ( 2011 ), 31-40."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press ( 1997 ).  E. Kushilevitz and N. Nisan. 1997. Communication Complexity. Cambridge University Press ( 1997 ).","DOI":"10.1017\/CBO9780511574948"},{"key":"e_1_3_2_1_14_1","volume-title":"Logik der Forschung: Zur Erkenntnistheorie der modernen Naturwissenschaft","author":"Popper K.","year":"1934","unstructured":"K. Popper . 1934. Logik der Forschung: Zur Erkenntnistheorie der modernen Naturwissenschaft . T\u00fcbingen : Siebeck ( 1934 ). K. Popper. 1934. Logik der Forschung: Zur Erkenntnistheorie der modernen Naturwissenschaft. T\u00fcbingen: Siebeck ( 1934 )."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301343"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"A. Razborov. 1992. On the Distributional Complexity of Disjointness. Theoretical Computer Science 106 ( 2 ) ( 1992 ) 385-390.  A. Razborov. 1992. On the Distributional Complexity of Disjointness. Theoretical Computer Science 106 ( 2 ) ( 1992 ) 385-390.","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_17_1","unstructured":"A. Sinclair. 2018. Randomness and Computation. UC Berkeley lecture notes ( 2018 ).  A. Sinclair. 2018. Randomness and Computation. UC Berkeley lecture notes ( 2018 )."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384243","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384243","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384243"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":17,"alternative-id":["10.1145\/3357713.3384243","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384243","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}