A note on multiparty communication complexity and the Hales-Jewett theorem

DOI10.1016/j.ipl.2018.07.002zbMath1478.68094arXiv1706.02277OpenAlexW2963779692WikidataQ129581020 ScholiaQ129581020MaRDI QIDQ1799572

Adi Shraibman

Publication date: 19 October 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1706.02277

zbMATH Keywords

computational complexityHales-Jewett theoremRamsey theory

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Ramsey theory (05D10) Communication complexity, information complexity (68Q11)

Cites Work

• Unnamed Item
• Unnamed Item
• A new proof of the density Hales-Jewett theorem
• The NOF multiparty communication complexity of composed functions
• Sets of integers that do not contain long arithmetic progressions
• Deducing the density Hales-Jewett theorem from an infinitary removal lemma
• On the power of small-depth threshold circuits
• A density version of the Hales-Jewett theorem for \(k=3\)
• An ergodic Szemerédi theorem for commuting transformations
• An improved construction of progression-free sets
• A density version of the Hales-Jewett theorem
• A Simple Proof of the Density Hales–Jewett Theorem
• A Note on Elkin’s Improvement of Behrend’s Construction
• Density Hales-Jewett and Moser numbers
• Languages with Bounded Multiparty Communication Complexity
• An Application of Hindman's Theorem to a Problem on Communication Complexity
• Communication Complexity
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity
• The Multiparty Communication Complexity of Exact-T: Improved Bounds and New Problems
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression

This page was built for publication: A note on multiparty communication complexity and the Hales-Jewett theorem