Equality is Far Weaker than Constant-Cost Communication

by Mika Göös, Nathaniel Harms, and Artur Riazanov

Theory of Computing, Volume 22(2272), pp. 1-16, 2026

Bibliography with links to cited articles

[1]   Mark Braverman and Omri Weinstein: A discrepancy lower bound for information complexity. Algorithmica, 76(3):846–864, 2016. [doi:10.1007/s00453-015-0093-8]

[2]   Arkadev Chattopadhyay, Shachar Lovett, and Marc Vinyals: Equality alone does not simulate randomness. In Proc. 34th Comput. Complexity Conf. (CCC’19), pp. 14:1–11. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. [doi:10.4230/LIPIcs.CCC.2019.14]

[3]   Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, and Morgan Shirley: A lower bound on the trace norm of Boolean matrices and its applications. In Proc. 16th Innovations in Theoret. Comp. Sci. Conf. (ITCS’25), pp. 37:1–15. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2025. [doi:10.4230/LIPIcs.ITCS.2025.37]

[4]   Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, and Morgan Shirley: Separation of the factorization norm and randomized communication complexity. Comput. Complexity, 34(2):17, 2025. Preliminary version in CCC’23. [doi:10.1007/S00037-025-00278-3]

[5]   Tsun Ming Cheung, Hamed Hatami, Rosie Zhao, and Itai Zilberstein: Boolean functions with small approximate spectral norm. Discrete Analysis, 6:1–22, 2024. [doi:10.19086/da.122971, arXiv:2409.10634]

[6]   Louis Esperet, Nathaniel Harms, and Andrey Kupavskii: Sketching distances in monotone graph classes. In Proc. 26th Internat. Conf. on Randomization and Computation (RANDOM’22), pp. 18:1–23. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2022. [doi:10.4230/LIPIcs.APPROX/RANDOM.2022.18]

[7]   Yuting Fang, Mika Göös, Nathaniel Harms, and Pooya Hatami: Constant-cost communication is not reducible to k-Hamming distance. In Proc. 57th STOC, pp. 565–571. ACM Press, 2025. [doi:10.1145/3717823.3718129]

[8]   Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, and Pooya Hatami: No complete problem for constant-cost randomized communication. In Proc. 56th STOC, pp. 1287–1298. ACM Press, 2024. [doi:10.1145/3618260.3649716]

[9]   Mika Göös, Nathaniel Harms, and Artur Riazanov: Equality is far weaker than constant-cost communication. In Proc. 29th Internat. Conf. on Randomization and Computation (RANDOM’25), pp. 58:1–14. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2025. [doi:10.4230/LIPIcs.APPROX/RANDOM.2025.58]

[10]   Lianna Hambardzumyan, Hamed Hatami, and Pooya Hatami: Dimension-free bounds and structural results in communication complexity. Israel J. Math., 253(2):555–616, 2023. [doi:10.1007/s11856-022-2365-8]

[11]   Nathaniel Harms: Universal communication, universal graphs, and graph labeling. In Proc. 11th Innovations in Theoret. Comp. Sci. Conf. (ITCS’20), pp. 33:1–27. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ITCS.2020.33]

[12]    Nathaniel Harms and Artur Riazanov: Better boosting of communication oracles, or not. In Proc. 44th Found. Softw. Techn. Theoret. Comp. Sci. Conf. (FSTTCS’24), pp. 25:1–24. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2024. [doi:10.4230/LIPIcs.FSTTCS.2024.25]

[13]   Nathaniel Harms, Sebastian Wild, and Viktor Zamaraev: Randomized communication and implicit graph representations. TheoretiCS, 4(20):1–81, 2025. Preliminary version in STOC’22. [doi:10.46298/THEORETICS.25.20]

[14]   Nathaniel Harms and Viktor Zamaraev: Randomized communication and implicit representations for matrices and graphs of small sign-rank. In Proc. 35th Ann. ACM–SIAM Symp. on Discrete Algorithms (SODA’24), pp. 1810–1833. SIAM, 2024. [doi:10.1137/1.9781611977912.72]

[15]   Hamed Hatami and Pooya Hatami: Guest column: Structure in communication complexity and constant-cost complexity classes. SIGACT News, 55(1):67–93, 2024. [doi:10.1145/3654780.3654788]

[16]   Eyal Kushilevitz and Noam Nisan: Communication complexity. Cambridge Univ. Press, 1996. [doi:10.1017/CBO9780511574948]

[17]   Noam Nisan: The communication complexity of threshold gates. In Dezső Miklós, Vera T. Sós, and Tamás Szőnyi, editors, Combinatorics, Paul Erdős is Eighty, Vol. I, volume 1 of Bolyai Society Mathematical Studies, pp. 301–315. J. Bolyai Math. Society, 1993. Facsimile of the entire volume is accessible at Rényi Institute. A preliminary version of this paper is available at the author’s website.

[18]   Toniann Pitassi, Morgan Shirley, and Adi Shraibman: The strength of equality oracles in communication. In Proc. 14th Innovations in Theoret. Comp. Sci. Conf. (ITCS’23), pp. 89:1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2023. [doi:10.4230/LIPIcs.ITCS.2023.89]

[19]   Anup Rao and Amir Yehudayoff: Communication Complexity and Applications. Cambridge Univ. Press, 2020. [doi:10.1017/9781108671644]

[20]   Tom Sanders: Boolean functions with small spectral norm, revisited. Math. Proc. Cambridge Phil. Soc., 167(2):335–344, 2019. [doi:10.1017/S030500411800035X]

[21]   Alexander Sherstov and Andrey Storozhenko: The communication complexity of approximating matrix rank. In Proc. 65th FOCS, pp. 433–462. IEEE Comp. Soc., 2024. [doi:10.1109/FOCS61266.2024.00035]

[22]   Srikanth Srinivasan and Amir Yehudayoff: The discrepancy of greater-than, 2023. [arXiv:2309.08703]

[23]   István Tomon: Factorization norms and Zarankiewicz problems, 2025. [arXiv:2502.18429]

[24]   Emanuele Viola: The communication complexity of addition. Combinatorica, 35(6):703–747, 2015. [doi:10.1007/s00493-014-3078-3]