Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-09T15:03:46.069Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  03 December 2003

Pavel Pudlák
Pavel Pudlák*
Affiliation:
Mathematical Institute, Academy of Sciences, Prague, Czech Republic
*
(e-mail: pudlak@math.cas.cz)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We consider the k-party communication complexity of the problem of determining if a word w is of the form , for fixed letters . Using the well-known theorem of Hindman (a Ramsey-type result about finite subsets of natural numbers), we prove that for and 5 the communication complexity of the problem increases with the length of the word w.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 12 , Issue 5-6: This issue contains volume twelve, parts five and six , November 2003 , pp. 661 - 670
Copyright
Copyright © Cambridge University Press 2003

Footnotes

†

Supported by grants A1019901 of the Academy of Sciences of the Czech Republic, No. 201/01/1195 of the Grant Agency of the Czech Republic, and project No. LN00A056 of the Ministry of Education of the Czech Republic.