Separating the k-party communication hierarchy: an application of the Zarankiewicz problem.
Thomas P. Hayes.
Manuscript, November 2001.
Abstract:
For every positive integer k, we construct an explicit family of
functions f:{0,1}n → {0,1}
which has (k + 1)-party communication complexity O(k)
under every partition of the input bits into k + 1 parts of equal size,
and k-party communication complexity Ω ( n / k4 2k )
under every partition of the input bits into k parts.
This improves an earlier hierarchy theorem due to V. Grolmusz.
Our construction relies on known explicit constructions for a
famous open problem of Zarankiewicz: find the maximum number
of edges in a graph on n vertices which does not contain
Ks,t
as a subgraph.