Paper Info
Title
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) -> {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.
Year
Venue
Keywords
2011
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE
communication complexity,extremal combinatorics,expander graphs
Field
DocType
Volume
Integer,Discrete mathematics,Combinatorics,Open problem,Vertex (geometry),Zarankiewicz problem,Communication complexity,Omega,Partition (number theory),Hierarchy,Mathematics
Journal
13.0
Issue
ISSN
Citations 
SP4.0
1462-7264
1
PageRank 
References 
Authors
0.37
3
1
Name
Order
Citations
PageRank
Thomas P. Hayes165954.21