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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2011, Vol. 13 no. 4 (4), pp.15--22
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00990498
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mardi 13 mai 2014 - 15:39:33
Dernière modification le : jeudi 7 septembre 2017 - 01:03:39
Document(s) archivé(s) le : lundi 10 avril 2017 - 22:12:28

Fichier

2048-6587-1-PB.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

69

Téléchargements de fichiers

252