首页    期刊浏览 2025年07月11日 星期五
登录注册

文章基本信息

  • 标题:On the Communication Complexity of High-Dimensional Permutations
  • 本地全文:下载
  • 作者:Nati Linial ; Toniann Pitassi ; Adi Shraibman
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:124
  • 页码:1-20
  • DOI:10.4230/LIPIcs.ITCS.2019.54
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要: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.
  • 关键词:High dimensional permutations; Number On the Forehead model; Additive combinatorics
国家哲学社会科学文献中心版权所有