An Application of Hindman's Theorem to a Problem on Communication Complexity
Pavel Pudlák · Combinatorics Probability Computing · 2003
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.