Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-00990498
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Tuesday, May 13, 2014 - 3:39:33 PM
Last modification on : Thursday, September 7, 2017 - 1:03:39 AM
Long-term archiving on: : Monday, April 10, 2017 - 10:12:28 PM

File

2048-6587-1-PB.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00990498, version 1

Collections

Citation

Thomas P. Hayes. Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 4 (4), pp.15--22. ⟨hal-00990498⟩

Share

Metrics

Record views

111

Files downloads

836