2026-08-16T15:14:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25117 2026-02-09T08:06:24Z ddc:004 open_access

Communication Complexity of Equality and Error-Correcting Codes Jacobs, Dale Jeang, John Podolskii, Vladimir Prior, Morgan Volkovich, Ilya communication complexity randomized communication complexity error-correcting codes We study the public-coin randomized communication complexity of the equality function. The communication complexity of this function is known to be low when the error probability is constant and the players have access to many random bits. The complexity grows, however, if the allowed error probability and the amount of randomness are restricted. We show that public-coin randomized protocols for equality and error-correcting codes are essentially the same object. That is, given a protocol for equality, we can construct a code, and vice versa. We substantially extend the protocol-implies-code direction: any protocol computing a function with a large fooling set can be converted into an error-correcting code. As a corollary, we show that among functions with a fooling set of size s, equality on log s bits has the least randomized communication complexity, regardless of the restrictions on the error probability and the amount of randomness. Finally, we use the connection to error-correcting codes to analyze the randomized communication complexity of equality for varying restrictions on the error probability and the amount of randomness. In most cases, we provide tight bounds. We pinpoint the setting in which tight bounds are still unknown. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Dale Jacobs and John Jeang and Vladimir Podolskii and Morgan Prior and Ilya Volkovich 2025 Is Part Of LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2025.37 urn:nbn:de:0030-drops-251175 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.37 eng https://creativecommons.org/licenses/by/4.0/legalcode