License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2019.54
URN: urn:nbn:de:0030-drops-101470
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/10147/
Go to the corresponding LIPIcs Volume Portal

Linial, Nati ; Pitassi, Toniann ; Shraibman, Adi

On the Communication Complexity of High-Dimensional Permutations

pdf-format:
LIPIcs-ITCS-2019-54.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{linial_et_al:LIPIcs:2018:10147,
  author =	{Nati Linial and Toniann Pitassi and Adi Shraibman},
  title =	{{On the Communication Complexity of High-Dimensional Permutations}},
  booktitle =	{10th Innovations in Theoretical Computer Science  Conference (ITCS 2019)},
  pages =	{54:1--54:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{124},
  editor =	{Avrim Blum},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10147},
  URN =		{urn:nbn:de:0030-drops-101470},
  doi =		{10.4230/LIPIcs.ITCS.2019.54},
  annote =	{Keywords: High dimensional permutations, Number On the Forehead model, Additive combinatorics}
}

Keywords: High dimensional permutations, Number On the Forehead model, Additive combinatorics
Collection: 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Issue Date: 2018
Date of publication: 08.01.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI