{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T01:57:56Z","timestamp":1780883876135,"version":"3.54.1"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:00:00Z","timestamp":1780876800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100000038","name":"NSERC","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Goergen Institute for Data Science at the University of Rochester"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1007\/s00453-026-01396-2","type":"journal-article","created":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:59:50Z","timestamp":1780880390000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Lower Bound on the Trace Norm of Boolean Matrices and its Applications"],"prefix":"10.1007","volume":"88","author":[{"given":"Tsun-Ming","family":"Cheung","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hamed","family":"Hatami","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kaave","family":"Hosseini","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandar","family":"Nikolov","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toniann","family":"Pitassi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Morgan","family":"Shirley","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,8]]},"reference":[{"key":"1396_CR1","unstructured":"Alon, N., Moran, S., Yehudayoff, A.: Sign rank versus vc dimension. In: Annual Conference Computational Learning Theory, (2015)"},{"key":"1396_CR2","doi-asserted-by":"crossref","unstructured":"Balla, I., Hambardzumyan, L., Tomon, I.: Factorization norms and an inverse theorem for MaxCut. (2025). Electronic Colloquium on Computational Complexity: TR25- 088. Pre-published","DOI":"10.1007\/s00208-026-03355-2"},{"key":"1396_CR3","doi-asserted-by":"publisher","unstructured":"Bose, R.C., Ray-Chaudhuri, D.K.: On a class of error correcting binary group codes. Information and Control 3.1 (1960), pp. 68\u201379. issn: 0019-9958. https:\/\/doi.org\/10.1016\/s0019-9958(60)90287-4","DOI":"10.1016\/s0019-9958(60)90287-4"},{"key":"1396_CR4","doi-asserted-by":"publisher","unstructured":"Bansal, N., Sinha, M.: K-forrelation optimally separates quantum and classical query complexity. Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. STOC 2021. Virtual, Italy: Association for Computing Machinery, (2021), pp. 1303\u20131316. isbn: 9781450380539. https:\/\/doi.org\/10.1145\/3406325.3451040","DOI":"10.1145\/3406325.3451040"},{"key":"1396_CR5","doi-asserted-by":"publisher","unstructured":"Chattopadhyay, A., Dahiya, Y., Mande, N.S., Radhakrishnan, J., Sanyal, S.: Randomized versus deterministic decision tree size. Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC \u201923. ACM, (2023). https:\/\/doi.org\/10.1145\/3564246.3585199","DOI":"10.1145\/3564246.3585199"},{"key":"1396_CR6","doi-asserted-by":"crossref","unstructured":"Chazelle, B.: The Discrepancy Method: Randomness and Complexity, Cambridge University Press (2001)","DOI":"10.1017\/CBO9780511626371"},{"key":"1396_CR7","unstructured":"Cheung, T.-M., Hatami, H., Hosseini, K., Shirley, M.: Separation of the factorization norm and randomized communication complexity. 38th Computational Complexity Conference (CCC 2023). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik. (2023)"},{"key":"1396_CR8","doi-asserted-by":"publisher","unstructured":"Cheung, T-M., Hatami, H., Zhao, R., Zilberstein, I.: Boolean functions with small approximate spectral norm. Discrete Analysis (2024). https:\/\/doi.org\/10.19086\/da.122971","DOI":"10.19086\/da.122971"},{"key":"1396_CR9","doi-asserted-by":"crossref","unstructured":"Chazelle, B., Lvov, A.: A trace bound for the hereditary discrepancy. In: Proceedings of the sixteenth annual symposium on Computational geometry, pp. 64\u201369. (2000)","DOI":"10.1145\/336154.336179"},{"key":"1396_CR10","unstructured":"Chattopadhyay, A., Lovett, S., Vinyals, M.: Equality alone does not simulate randomness. 34th Computational Complexity Conference (CCC 2019). (2019)"},{"issue":"4","key":"1396_CR11","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/3396695","volume":"67","author":"A Chattopadhyay","year":"2020","unstructured":"Chattopadhyay, A., Mande, N.S., Sherif, S.: The log-approximate-rank conjecture is false. J. ACM 67(4), 23:1-23:28 (2020). https:\/\/doi.org\/10.1145\/3396695","journal-title":"J. ACM"},{"key":"1396_CR12","doi-asserted-by":"publisher","unstructured":"Davidson, K.R., Donsig, A.P.: Norms of Schur multipliers. Ill. J. Math. 51(3), (2007). https:\/\/doi.org\/10.1215\/ijm\/1258131101. issn: 0019-2082","DOI":"10.1215\/ijm\/1258131101"},{"key":"1396_CR13","doi-asserted-by":"publisher","unstructured":"G\u00f6\u00f6s, M., Harms, N., Riazanov, A.: Equality is far weaker than constant-cost communication. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM 2025). Ed. by Alina Ene and Eshan Chattopadhyay. Vol. 353. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, (2025), 58:1\u201358:14. isbn: 978-3-95977-397-3. https:\/\/doi.org\/10.4230\/LIPIcs.APPROX\/RANDOM.2025.58","DOI":"10.4230\/LIPIcs.APPROX\/RANDOM.2025.58"},{"key":"1396_CR14","doi-asserted-by":"publisher","unstructured":"G\u00f6\u00f6s, M., Pitassi, T., Watson, T.: The landscape of communication complexity classes. computational complexity 27(2), 245\u2013304 . https:\/\/doi.org\/10.1007\/s00037-018-0166-6. issn: 1420-8954","DOI":"10.1007\/s00037-018-0166-6"},{"issue":"1","key":"1396_CR15","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1007\/s00039-008-0654-y","volume":"18","author":"B Green","year":"2008","unstructured":"Green, B., Sanders, T.: Boolean functions with small spectral norm. Geom. Funct. Anal. 18(1), 144\u2013162 (2008). https:\/\/doi.org\/10.1007\/s00039-008-0654-y. (issn: 1420-8970)","journal-title":"Geom. Funct. Anal."},{"key":"1396_CR16","doi-asserted-by":"publisher","unstructured":"Girish, U., Tal, A., Wu, K.: Fourier growth of parity decision trees. 36th Computational Complexity Conference (CCC 2021). Vol. 200. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 39:1\u201339:36. (2021) isbn: 978-3-95977-193-1. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2021. 39","DOI":"10.4230\/LIPIcs.CCC.2021."},{"issue":"2","key":"1396_CR17","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1007\/s11856-022-2365-8","volume":"253","author":"L Hambardzumyan","year":"2023","unstructured":"Hambardzumyan, L., Hatami, H., Hatami, P.: Dimension-free bounds and structural results in communication complexity. Israel J. Math. 253(2), 555\u2013616 (2023)","journal-title":"Israel J. Math."},{"key":"1396_CR18","unstructured":"Hardy, G.H., Littlewood, J.E., Polya, G.: Cambridge Mathematical Library: Inequalities, Cambridge University Press (1988)"},{"key":"1396_CR19","first-page":"147","volume":"2","author":"A Hocquenghem","year":"1959","unstructured":"Hocquenghem, A.: Codes correcteurs d\u2019erreurs. Chiffres 2, 147\u2013156 (1959)","journal-title":"Codes correcteurs d\u2019erreurs. Chiffres"},{"key":"1396_CR20","doi-asserted-by":"publisher","unstructured":"Kushilevitz, E., Mansour, Y.: Learning decision trees using the Fourier spectrum. Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing. STOC \u201991. New Orleans, Louisiana, USA: Association for Computing Machinery, pp. 455\u2013464 (1991). isbn: 0897913973. https:\/\/doi.org\/10.1145\/103418.103466","DOI":"10.1145\/103418.103466"},{"issue":"1","key":"1396_CR21","doi-asserted-by":"publisher","first-page":"50","DOI":"10.4064\/cm-3-1-50-57","volume":"3","author":"T K\u00f3vari","year":"1954","unstructured":"K\u00f3vari, T., S\u00f3s, V., Tur\u00e1n, P.: On a problem of K. Zarankiewicz. Colloquium Mathematicum 3(1), 50\u201357 (1954). https:\/\/doi.org\/10.4064\/cm-3-1-50-57. (issn: 1730-6302)","journal-title":"Zarankiewicz. Colloquium Mathematicum"},{"key":"1396_CR22","doi-asserted-by":"crossref","unstructured":"Nisan, N.: CREW PRAMs and decision trees. In: Proceedings of the twenty-first annual ACM symposium on Theory of computing, pp. 327\u2013335. (1989)","DOI":"10.1145\/73007.73038"},{"key":"1396_CR23","doi-asserted-by":"publisher","unstructured":"Pitassi, T., Shirley, M., Shraibman, A.: The strength of equality oracles in communication. 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Vol. 251. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 89:1\u201389:19. (2023) isbn: 978-3-95977-263-1. https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2023.89","DOI":"10.4230\/LIPIcs.ITCS.2023.89"},{"issue":"02","key":"1396_CR24","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1017\/S030500411800035X","volume":"167","author":"T Sanders","year":"2019","unstructured":"Sanders, T.: Boolean functions with small spectral norm. revisited. en. Math. Proc. Camb. Philos. Soc. 167(02), 335\u2013344 (2019)","journal-title":"revisited. en. Math. Proc. Camb. Philos. Soc."},{"issue":"1","key":"1396_CR25","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s00037-015-0110-y","volume":"26","author":"A Shpilka","year":"2017","unstructured":"Shpilka, A., Tal, A., Volk, B.L.: On the structure of Boolean functions with small spectral norm. Comput. Complex. 26(1), 229\u2013273 (2017). https:\/\/doi.org\/10.1007\/s00037-015-0110-y. (issn: 1420-8954)","journal-title":"Comput. Complex."},{"key":"1396_CR26","doi-asserted-by":"publisher","unstructured":"Tal, A.: Tight bounds on the Fourier spectrum of AC0. 32nd Computational Complexity Conference (CCC 2017). Vol. 79. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:31. (2017) isbn: 978-3-95977-040-8. https:\/\/doi.org\/10.4230\/LIPIcs.CCC.2017.15","DOI":"10.4230\/LIPIcs.CCC.2017.15"},{"key":"1396_CR27","unstructured":"Tomon, I.: Factorization norms and Zarankiewicz problems. (2025). arXiv: 2502.18429 [math]. Pre-published."},{"key":"1396_CR28","doi-asserted-by":"publisher","unstructured":"Tsang, H.Y., Wong, C.H., Xie, N., Zhang, S.: Fourier sparsity, spectral norm, and the log-rank conjecture. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. pp. 658\u2013667, (2013). https:\/\/doi.org\/10.1109\/FOCS.2013.76","DOI":"10.1109\/FOCS.2013.76"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01396-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01396-2","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01396-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,8]],"date-time":"2026-06-08T00:59:53Z","timestamp":1780880393000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01396-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,8]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["1396"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01396-2","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,6,8]]},"assertion":[{"value":"24 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 May 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"54"}}