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 problemArticle

Authors: Thomas P. Hayes 1

  • 1 UNM Computer Science department [New Mexico]

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]

1 Document citing this article

Consultation statistics

This page has been seen 307 times.
This article's PDF has been downloaded 450 times.