Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-16T15:26:02.295Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

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.