Stasys Jukna
On communication games with more than two players
Abstract
A k-player game is a communication game between k parties, each of which
has an access to a half of input bits. 2-player games were introduced by
Yao (1981) and are known as best-partition two-party games. We first describe
a lower bounds argument for this case, based on computing the term-rank
and clique-number of communica- tion matrices. Using this argument we exhibit
an explicit function on n variables such that any 2-players protocol for
it requires $\Omega(\sqrt{n})$ bits of communication, whereas 3 players need
to communicate only constant number of bits. We then consider another restriction:
we allow any number of players but require that every singular input bit
is accessable to at most $k$ of these players. We prove that, for small values
of $k$, no such protocol can recognize codewords of some linear codes of
length $n$ using less than $\Omega(\sqrt{n})$ bits of communication.
Back
to my home page