de.mpg.escidoc.pubman.appbase.FacesBean
English

Item

ITEM ACTIONSEXPORT

Released

Report

On multi-party communication complexity of random functions

MPS-Authors

Grolmusz,  Vince
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-93-162.pdf
(Any fulltext), 7MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Grolmusz, V.(1993). On multi-party communication complexity of random functions (MPI-I-93-162). Saarbrücken: Max-Planck-Institut für Informatik.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B775-6
Abstract
We prove that almost all Boolean function has a high $k$--party communication complexity. The 2--party case was settled by {\it Papadimitriou} and {\it Sipser}. Proving the $k$--party case needs a deeper investigation of the underlying structure of the $k$--cylinder--intersections; (the 2--cylinder--intersections are the rectangles). \noindent First we examine the basic properties of $k$--cylinder--intersections, then an upper estimation is given for their number, which facilitates to prove the lower--bound theorem for the $k$--party communication complexity of randomly chosen Boolean functions. In the last section we extend our results to the $\varepsilon$--distributional communication complexity of random functions.