2026-08-18T16:44:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10147 2024-03-06T10:45:29Z ddc:004 open_access

On the Communication Complexity of High-Dimensional Permutations Linial, Nati Pitassi, Toniann Shraibman, Adi High dimensional permutations Number On the Forehead model Additive combinatorics We study the multiparty communication complexity of high dimensional permutations in the Number On the Forehead (NOF) model. This model is due to Chandra, Furst and Lipton (CFL) who also gave a nontrivial protocol for the Exactly-n problem where three players receive integer inputs and need to decide if their inputs sum to a given integer n. There is a considerable body of literature dealing with the same problem, where (N,+) is replaced by some other abelian group. Our work can be viewed as a far-reaching extension of this line of research. We show that the known lower bounds for that group-theoretic problem apply to all high dimensional permutations. We introduce new proof techniques that reveal new and unexpected connections between NOF communication complexity of permutations and a variety of well-known problems in combinatorics. We also give a direct algorithmic protocol for Exactly-n. In contrast, all previous constructions relied on large sets of integers without a 3-term arithmetic progression. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nati Linial and Toniann Pitassi and Adi Shraibman 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.54 urn:nbn:de:0030-drops-101470 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.54 eng https://creativecommons.org/licenses/by/3.0/legalcode