{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:05:26Z","timestamp":1764781526966,"version":"3.46.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T00:00:00Z","timestamp":1761523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"DOI":"10.1007\/s00037-025-00278-3","type":"journal-article","created":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T15:31:12Z","timestamp":1761579072000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Separation of the Factorization Norm and Randomized Communication Complexity"],"prefix":"10.1007","volume":"34","author":[{"given":"Tsun-Ming","family":"Cheung","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hamed","family":"Hatami","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kaave","family":"Hosseini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morgan","family":"Shirley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,27]]},"reference":[{"key":"278_CR1","doi-asserted-by":"crossref","unstructured":"Shalev Ben-David, Adam Bouland, Ankit Garg & Robin\nKothari (2018). Classical Lower Bounds from Quantum Upper\nBounds. 2018 IEEE 59th Annual Symposium on Foundations of Computer\nScience (FOCS) 339\u2013349.","DOI":"10.1109\/FOCS.2018.00040"},{"key":"278_CR2","unstructured":"Arkadev Chattopadhyay, Shachar Lovett & Marc Vinyals\n(2019). Equality alone does not simulate randomness. In 34th Computational\nComplexity Conference (CCC 2019)."},{"key":"278_CR3","unstructured":"Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini & Morgan\nShirley (2023). Separation of the factorization norm and randomized\ncommunication complexity. In 38th Computational Complexity Conference\n(CCC 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"278_CR4","doi-asserted-by":"crossref","unstructured":"Alexander Edmonds, Aleksandar Nikolov & Jonathan Ullman\n(2020). The Power of Factorization Mechanisms in Local and\nCentral Differential Privacy. In Proceedings of the 52nd Annual ACM\nSIGACT Symposium on Theory of Computing, 425\u2013438. Association for\nComputing Machinery, New York, NY, USA. ISBN 978-1-4503-6979-4.","DOI":"10.1145\/3357713.3384297"},{"key":"278_CR5","doi-asserted-by":"crossref","unstructured":"Mika G\u00f6\u00f6s, Toniann Pitassi & Thomas Watson (2018). The\nLandscape of Communication Complexity Classes. computational complexity\n27(2), 245\u2013304. ISSN 1420-8954. URL http:\/\/dx.doi.org\/10.1007\/s00037-018-0166-6.","DOI":"10.1007\/s00037-018-0166-6"},{"key":"278_CR6","doi-asserted-by":"crossref","unstructured":"Ben Green & Tom Sanders (2008). Boolean functions with small\nspectral norm. Geometric and Functional Analysis 18(1), 144\u2013162.","DOI":"10.1007\/s00039-008-0654-y"},{"key":"278_CR7","doi-asserted-by":"crossref","unstructured":"Lianna Hambardzumyan, Hamed Hatami & Pooya Hatami\n(2023). Dimension-free bounds and structural results in communication\ncomplexity. Israel Journal of Mathematics 253(2), 555\u2013616.","DOI":"10.1007\/s11856-022-2365-8"},{"key":"278_CR8","unstructured":"Hamed Hatami, Pooya Hatami, William Pires, Ran Tao & Rosie\nZhao (2022). Lower Bound Methods for Signrank and Their Limitations.\nIn Approximation, Randomization, and Combinatorial Optimization.\nAlgorithms a, volume 245, 22:1\u201322:24."},{"key":"278_CR9","unstructured":"Monika Henzinger & Jalaj Upadhyay (2022). Constant matters:\nFine-grained Complexity of Differentially Private Continual\nObservation Using Completely Bounded Norms. arXiv preprint\narXiv:2202.11205."},{"key":"278_CR10","doi-asserted-by":"crossref","unstructured":"Wei Huang, Yaoyun Shi, Shengyu Zhang & Yufan Zhu (2006).\nThe communication complexity of the Hamming distance problem. Inform.\nProcess. Lett. 99(4), 149\u2013153. ISSN 0020-0190.","DOI":"10.1016\/j.ipl.2006.01.014"},{"key":"278_CR11","doi-asserted-by":"crossref","unstructured":"Hartmut Klauck (2007). Lower bounds for quantum communication\ncomplexity. SIAM Journal on Computing 37(1), 20\u201346.","DOI":"10.1137\/S0097539702405620"},{"key":"278_CR12","doi-asserted-by":"crossref","unstructured":"Eyal Kushilevitz & Noam Nisan (1997). Communication complexity.\nCambridge University Press, Cambridge. ISBN 0-521-56067-5,\nxiv+189 .","DOI":"10.1016\/S0065-2458(08)60342-3"},{"key":"278_CR13","doi-asserted-by":"crossref","unstructured":"Troy Lee, Adi Shraibman & Robert \u0160palek (2008). A Direct\nProduct Theorem for Discrepancy. In 2008 23rd Annual IEEE Conference\non Computational Complexity, 71\u201380.","DOI":"10.1109\/CCC.2008.25"},{"key":"278_CR14","doi-asserted-by":"crossref","unstructured":"Nati Linial & Adi Shraibman (2009). Lower bounds in communication\ncomplexity based on factorization norms. Random Structures &\nAlgorithms 34(3), 368\u2013394.","DOI":"10.1002\/rsa.20232"},{"key":"278_CR15","unstructured":"Ji\u0159\u00ed Matou\u0161ek, Aleksandar Nikolov & Kunal Talwar (2020).\nFactorization norms and hereditary discrepancy. International Mathematics\nResearch Notices 2020(3), 751\u2013780."},{"key":"278_CR16","doi-asserted-by":"crossref","unstructured":"Shanmugavelayutham Muthukrishnan & Aleksandar Nikolov\n(2012). Optimal private halfspace counting via discrepancy. In Proceedings\nof the forty-fourth annual ACM symposium on Theory of computing,\n1285\u20131292.","DOI":"10.1145\/2213977.2214090"},{"key":"278_CR17","doi-asserted-by":"crossref","unstructured":"Ramamohan Paturi & Janos Simon (1986). Probabilistic communication\ncomplexity. Journal of Computer and System Sciences 33(1),\n106\u2013123.","DOI":"10.1016\/0022-0000(86)90046-2"},{"key":"278_CR18","unstructured":"Toniann Pitassi, Morgan Shirley & Adi Shraibman (2023). The\nStrength of Equality Oracles in Communication. In 14th Innovations\nin Theoretical Computer Science Conference (ITCS 2023), Yael Tauman\nKalai, editor, volume 251 of Leibniz International Proceedings in\nInformatics (LIPIcs), 89:1\u201389:19. Schloss Dagstuhl \u2013 Leibniz-Zentrum\nf\u00fcr Informatik, Dagstuhl, Germany. ISBN 978-3-95977-263-1. ISSN\n1868-8969."},{"key":"278_CR19","doi-asserted-by":"crossref","unstructured":"Alexander A Razborov (2003). Quantum communication complexity\nof symmetric predicates. Izvestiya: Mathematics 67(1), 145.","DOI":"10.1070\/IM2003v067n01ABEH000422"},{"key":"278_CR20","unstructured":"Suhail Sherif (2021). Communication Complexity and Quantum Optimization\nLower Bounds via Query Complexity. Ph.D. thesis, Tata Institute\nof Fundamental Research, Mumbai."},{"key":"278_CR21","doi-asserted-by":"crossref","unstructured":"J\u00f3zsef Solymosi (2009). Incidences and the spectra of graphs. In\nCombinatorial number theory and additive group theory, 299\u2013314.\nSpringer.","DOI":"10.1007\/978-3-7643-8962-8_22"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00278-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00278-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00278-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:22Z","timestamp":1764781222000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00278-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,27]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["278"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00278-3","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,10,27]]},"assertion":[{"value":"31 August 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"17"}}