Discrete Mathematics & Theoretical Computer Science, Vol 13, No 4

Font Size:  Small  Medium  Large

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

Thomas P Hayes


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 K. Zarankiewicz, namely, to find the maximum number of edges in a graph on n vertices that does not contain Ks,t as a subgraph.

Full Text: PDF PostScript