Thomas P. Hayes - Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem

dmtcs:546 - Discrete Mathematics & Theoretical Computer Science, November 13, 2011, Vol. 13 no. 4 - https://doi.org/10.46298/dmtcs.546
Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem

Authors: Thomas P. Hayes

For every positive integer k, we construct an explicit family of functions f : \0, 1\(n) -\textgreater \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 Omega (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,K-t as a subgraph.


Volume: Vol. 13 no. 4
Published on: November 13, 2011
Accepted on: June 9, 2015
Submitted on: February 18, 2011
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]


Share

Consultation statistics

This page has been seen 128 times.
This article's PDF has been downloaded 290 times.