An Application of Hindman's Theorem to a Problem on Communication Complexity

DOI10.1017/S0963548303005790MaRDI QIDQ4655908zbMATH OpenOpenAlexFDO

Authors Pavel Pudlák

Publication date 8 March 2005

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/s0963548303005790

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Ramsey theory (05D10)

Recommendations

• A note on multiparty communication complexity and the Hales-Jewett theorem
• scientific article; zbMATH DE number 6292585
• The NOF multiparty communication complexity of composed functions
• scientific article; zbMATH DE number 3881884
• A simple proof and some difficult examples for Hindman's theorem

Cited in

(4)

• On Toda’s Theorem in Structural Communication Complexity
• A note on multiparty communication complexity and the Hales-Jewett theorem
• The NOF multiparty communication complexity of composed functions
• MONOIDS AND COMPUTATIONS

This page was built for publication: An Application of Hindman's Theorem to a Problem on Communication Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4655908)