Document Open Access Logo

On the Communication Complexity of High-Dimensional Permutations

Authors Nati Linial, Toniann Pitassi, Adi Shraibman

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2019.54.pdf
  • Filesize: 0.56 MB
  • 20 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Communication complexity
Keywords
  • High dimensional permutations
  • Number On the Forehead model
  • Additive combinatorics

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Nati Linial, Toniann Pitassi, and Adi Shraibman. On the Communication Complexity of High-Dimensional Permutations. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 54:1-54:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.54

Author Details

Nati Linial
  • Hebrew University of Jerusalem, Jerusalem, Israel
Toniann Pitassi
  • University of Toronto, Toronto, Canada and IAS, Princeton, U.S.A.
Adi Shraibman
  • The Academic College of Tel-Aviv-Yaffo, Tel-Aviv, Israel

Funding

  • Linial, Nati: Supported in part by ERC grant 339096, High-dimensional combinatorics.

References

  1. A. Ada, A. Chattopadhyay, O. Fawzi, and P. Nguyen. The NOF multiparty communication complexity of composed functions. computational complexity, 24(3):645-694, 2015. Google Scholar
  2. M. Ajtai and E. Szemerédi. Sets of lattice points that form no squares. Stud. Sci. Math. Hungar, 9(1975):9-11, 1974. Google Scholar
  3. N. Alon. Testing subgraphs in large graphs. Random Structures &Algorithms, 21(3-4):359-370, 2002. Google Scholar
  4. N. Alon, A. Moitra, and B. Sudakov. Nearly complete graphs decomposable into large induced matchings and their applications. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1079-1090. ACM, 2012. Google Scholar
  5. L. Babai, T. Hayes, and P. Kimmel. The cost of the missing bit: communication complexity with help. Combinatorica, 21:455-488, 2001. Google Scholar
  6. L. Babai, N. Nisan, and M. Szegedy. Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-offs. Journal of Computer and System Sciences, 45:204-232, 1992. Google Scholar
  7. P. Beame, M. David, T. Pitassi, and P. Woelfel. Separating deterministic from randomized NOF multiparty communication complexity. In Proceedings of the 34th International Colloquium On Automata, Languages and Programming, Lecture Notes in Computer Science. Springer-Verlag, 2007. Google Scholar
  8. P. Beame, T. Pitassi, and N. Segerlind. Lower bounds for Lovász-Schrijver systems and beyond follow from multiparty communication complexity. SIAM Journal on Computing, 37(3):845-869, 2006. Google Scholar
  9. F. A. Behrend. On sets of integers which contain no three terms in arithmetical progression. Proceedings of the National Academy of Sciences, 32(12):331-332, 1946. Google Scholar
  10. R. Beigel, W. Gasarch, and J. Glenn. The multiparty communication complexity of Exact-T: Improved bounds and new problems. In International Symposium on Mathematical Foundations of Computer Science, pages 146-156. Springer, 2006. Google Scholar
  11. K. Bibak. Additive Combinatorics: With a View Towards Computer Science and Cryptography - An Exposition. In Number Theory and Related Fields, In Memory of Alf van der Poorten, pages 99-128. Springer, 2013. Google Scholar
  12. Y. Birk, N. Linial, and R. Meshulam. On the uniform-traffic capacity of single-hop interconnections employing shared directional multichannels. IEEE Transactions on Information Theory, 39(1):186-191, 1993. Google Scholar
  13. A. Chandra, M. Furst, and R. Lipton. Multi-party protocols. In Proceedings of the 15th ACM Symposium on the Theory of Computing, pages 94-99. ACM, 1983. Google Scholar
  14. E. Croot, V. Lev, and P. Pach. Progression-free sets in ℤ₄ⁿ are exponentially small. arXiv preprint, 2016. URL: http://arxiv.org/abs/1605.01506.
  15. Z. Dvir. On the size of Kakeya sets in Finite Fields. J. Amer. Math Soc., pages 1093-1097, 2009. Google Scholar
  16. M. Elkin. An improved construction of progression-free sets. In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pages 886-905. Society for Industrial and Applied Mathematics, 2010. Google Scholar
  17. J. S. Ellenberg and D. G. On large subsets of 𝔽_q^ n with no three-term arithmetic progression. Annals of Mathematics, 185(1):339-343, 2017. Google Scholar
  18. J. Fox. A new proof of the graph removal lemma. Annals of Mathematics, pages 561-579, 2011. Google Scholar
  19. H. Furstenberg and Y. Katznelson. A density version of the Hales-Jewett theorem. Journal d'Analyse Mathematique, 57(1):64-119, 1991. Google Scholar
  20. R. Graham and J. Solymosi. Monochromatic equilateral right triangles on the integer grid. In Topics in discrete mathematics, pages 129-132. Springer, 2006. Google Scholar
  21. R. L. Graham, B. L. Rothschild, and J. H. Spencer. Ramsey theory, volume 20. John Wiley &Sons, 1990. Google Scholar
  22. V. Grolmusz. The BNS lower bound for multi-party protocols is nearly optimal. Information and computation, 112(1):51-54, 1994. Google Scholar
  23. J. Håstad and M. Goldmann. On the power of small-depth threshold circuits. Computational Complexity, 1:113-129, 1991. Google Scholar
  24. J. Håstad and A. Wigderson. Simple analysis of graph tests for linearity and PCP. Random Structures &Algorithms, 22(2):139-160, 2003. Google Scholar
  25. P. Keevash. The existence of designs II. arXiv preprint, 2018. URL: http://arxiv.org/abs/1802.05900.
  26. E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, 1997. Google Scholar
  27. N. Linial and Z. Luria. An upper bound on the number of high-dimensional permutations. Combinatorica, 34(4):471-486, 2014. Google Scholar
  28. L. Lovász. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383-390, 1975. Google Scholar
  29. S. Lovett. Additive Combinatorics and its Applications in Theoretical Computer Science. Theory of Computing, Graduate Surveys, 8:1-55, 2017. Google Scholar
  30. N. Nisan and A. Widgerson. Rounds in communication complexity revisited. In Proceedings of ACM STOC, pages 419-429. ACM, 1991. Google Scholar
  31. D.H.J. Polymath. A new proof of the density Hales-Jewett theorem. arXiv preprint, 2009. URL: http://arxiv.org/abs/0910.3926.
  32. K. F. Roth. On certain sets of integers. Journal of the London Mathematical Society, 1(1):104-109, 1953. Google Scholar
  33. I. Ruzsa and E. Szemerédi. Triple systems with no six points carrying three triangles. Combinatorics (Keszthely, 1976), Coll. Math. Soc. J. Bolyai, 18:939-945, 1978. Google Scholar
  34. I. D. Shkredov. On a two-dimensional analogue of Szemerédi’s theorem in Abelian groups. Izvestiya: Mathematics, 73(5):1033-1075, 2009. Google Scholar
  35. A. Shraibman. A Note on Multiparty Communication Complexity and the Hales-Jewett Theorem. arXiv preprint, 2017. URL: http://arxiv.org/abs/1706.02277.
  36. J. Solymosi. Note on a Generalization of Roth’s Theorem. In Discrete and Computational Geometry: The Goodman-Pollack Festschrift, pages 825-827. Springer Berlin Heidelberg, Berlin, Heidelberg, 2003. Google Scholar
  37. P. Tesson. An application of the Hales-Jewett Theorem to multiparty communication complexity, 2004. Google Scholar
  38. L. Trevisan. Guest column: additive combinatorics and theoretical computer science. SIGACT News, 40(2):50-66, 2009. Google Scholar
  39. J. H. van Lint and R. M. Wilson. A course in combinatorics. Cambridge university press, 2001. Google Scholar
  40. A. Yao. On ACC and threshold circuits. In Proceedings of the 31st IEEE Symposium on Foundations of Computer Science, pages 619-627. IEEE, 1990. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact