{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T23:12:40Z","timestamp":1775085160855,"version":"3.50.1"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T00:00:00Z","timestamp":1666915200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T00:00:00Z","timestamp":1666915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00037-022-00232-7","type":"journal-article","created":{"date-parts":[[2022,10,28]],"date-time":"2022-10-28T11:07:15Z","timestamp":1666955235000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Quantum versus Randomized Communication Complexity, with Efficient Players"],"prefix":"10.1007","volume":"31","author":[{"given":"Uma","family":"Girish","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Raz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avishay","family":"Tal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,28]]},"reference":[{"key":"232_CR1","doi-asserted-by":"crossref","unstructured":"Scott Aaronson (2010). BQP and the Polynomial Hierarchy. In\nProceedings of the 42nd ACM Symposium on Theory of Computing,\nCambridge, Massachusetts, USA, 5\u20138 June 2010, 141\u2013150. ACM.","DOI":"10.1145\/1806689.1806711"},{"key":"232_CR2","unstructured":"Scott Aaronson (2010). BQP and the Polynomial Hierarchy. In\nProceedings of the 42nd ACM Symposium on Theory of Computing,\nCambridge, Massachusetts, USA, 5\u20138 June 2010, 141\u2013150. ACM.\nScott Aaronson & Andris Ambainis (2015). Forrelation: A Problem\nthat Optimally Separates Quantum from Classical Computing. In\nProceedings of the Forty-Seventh Annual ACM on Symposium on Theory\nof Computing, Portland, OR, USA, June 14\u201317, 2015, 307\u2013316.\nACM."},{"key":"232_CR3","doi-asserted-by":"crossref","unstructured":"Ziv Bar-Yossef, T. S. Jayram & Iordanis Kerenidis (2004). Exponential\nSeparation of Quantum and Classical One-way Communication\nComplexity. In Proceedings of the 36th Annual ACM Symposium on\nTheory of Computing, Chicago, IL, USA, June 13\u201316, 2004, 128\u2013137.\nACM.","DOI":"10.1145\/1007352.1007379"},{"key":"232_CR4","doi-asserted-by":"crossref","unstructured":"Harry Buhrman, Richard Cleve & Avi Wigderson (1998). Quantum\nvs. Classical Communication and Computation. In Proceedings of\nthe Thirtieth Annual ACM Symposium on the Theory of Computing,\nDallas, Texas, USA, May 23\u201326, 1998, 63\u201368. ACM.","DOI":"10.1145\/276698.276713"},{"key":"232_CR5","unstructured":"Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth,\nOr Meir & Toniann Pitassi (2019a). Query-To-Communication\nLifting for BPP Using Inner Product. In 46th International Colloquium\non Automata, Languages, and Programming, July 9\u201312, 2019,\nPatras, Greece, volume 132 of LIPIcs, 35:1\u201335:15. Schloss Dagstuhl -\nLeibniz-Zentrum f\u00fcr Informatik."},{"key":"232_CR6","unstructured":"Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini &\nShachar Lovett (2018). Pseudorandom Generators from Polarizing\nRandom Walks. In 33rd Computational Complexity Conference, June\n22\u201324, 2018, San Diego, CA, USA, volume 102 of LIPIcs, 1:1\u20131:21.\nSchloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"232_CR7","unstructured":"Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett &\nAvishay Tal (2019b). Pseudorandom Generators from the Second\nFourier Level and Applications to AC0 with Parity Gates. In 10th Innovations\nin Theoretical Computer Science Conference, January 10\u201312,\n2019, San Diego, California, USA, volume 124 of LIPIcs, 22:1\u201322:15.\nSchloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik."},{"key":"232_CR8","doi-asserted-by":"crossref","unstructured":"Dmitry Gavinsky (2016). Entangled Simultaneity versus Classical\nInteractivity in Communication Complexity. In Proceedings of the 48th\nAnnual ACM SIGACT Symposium on Theory of Computing, Cambridge,\nMA, USA, June 18\u201321, 2016, 877\u2013884. ACM.","DOI":"10.1145\/2897518.2897545"},{"key":"232_CR9","doi-asserted-by":"crossref","unstructured":"Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz\n& Ronald de Wolf (2007). Exponential Separations for One-way\nQuantum Communication Complexity, with applications to cryptography.\nIn Proceedings of the 39th Annual ACM Symposium on Theory of\nComputing, San Diego, California, USA, June 11\u201313, 2007, 516\u2013525.\nACM.","DOI":"10.1145\/1250790.1250866"},{"key":"232_CR10","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2017). Query-to-\nCommunication Lifting for BPP. In 58th IEEE Annual Symposium on\nFoundations of Computer Science, Berkeley, CA, USA, October 15\u201317,\n2017, 132\u2013143. IEEE Computer Society.","DOI":"10.1109\/FOCS.2017.21"},{"key":"232_CR11","doi-asserted-by":"crossref","unstructured":"Hamed Hatami, Kaave Hosseini & Shachar Lovett (2016). Structure\nof Protocols for XOR Functions. In IEEE 57th Annual Symposium\non Foundations of Computer Science, 9\u201311 October 2016, Hyatt Regency,\nNew Brunswick, New Jersey, USA, 282\u2013288. IEEE Computer\nSociety.","DOI":"10.1109\/FOCS.2016.38"},{"key":"#cr-split#-232_CR12.1","doi-asserted-by":"crossref","unstructured":"Ryan O'Donnell (2014). Analysis of Boolean Functions. Cambridge","DOI":"10.1017\/CBO9781139814782"},{"key":"#cr-split#-232_CR12.2","unstructured":"University Press 2014. ISBN 978-1-10-703832-5, pp. I-XX, 1-423."},{"key":"232_CR13","doi-asserted-by":"crossref","unstructured":"Ran Raz (1995). Fourier Analysis for Probabilistic Communication\nComplexity. Comput. Complex. 5(3\/4), 205\u2013221.","DOI":"10.1007\/BF01206318"},{"key":"232_CR14","doi-asserted-by":"crossref","unstructured":"Ran Raz (1999). Exponential Separation of Quantum and Classical\nCommunication Complexity. In Proceedings of the Thirty-First Annual\nACM Symposium on Theory of Computing, May 1\u20134, 1999, Atlanta,\nGeorgia, USA, 358\u2013367. ACM.","DOI":"10.1145\/301250.301343"},{"key":"232_CR15","doi-asserted-by":"crossref","unstructured":"Ran Raz & Avishay Tal (2019). Oracle Separation of BQP and PH.\nIn Proceedings of the 51st Annual ACM SIGACT Symposium on Theory\nof Computing, Phoenix, AZ, USA, June 23\u201326, 2019, 13\u201323. ACM.","DOI":"10.1145\/3313276.3316315"},{"key":"232_CR16","doi-asserted-by":"crossref","unstructured":"Oded Regev & Bo\u2019az Klartag (2011). Quantum One-way Communication\ncan be Exponentially Stronger than Classical Communication.\nIn Proceedings of the 43rd ACM Symposium on Theory of Computing,\nSan Jose, CA, USA, 6\u20138 June 2011, 31\u201340. ACM.","DOI":"10.1145\/1993636.1993642"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00232-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00232-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00232-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T15:29:10Z","timestamp":1669303750000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00232-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,28]]},"references-count":17,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["232"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00232-7","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,28]]},"assertion":[{"value":"10 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 October 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"17"}}