### Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem

*Thomas P Hayes*

#### 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 / k^{4}2^{k}) 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 K. Zarankiewicz, namely, to find the maximum number of edges in a graph on n vertices that does not contain K_{s,t}as a subgraph.Full Text: PDF PostScript