MPI-INF/SWS Research Reports 1991-2021

2. Number - only D1


On multi-party communication complexity of random functions

Grolmusz, Vince

December 1993, 10 pages.

Status: available - back from printing

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.

URL to this document:

Hide details for BibTeXBibTeX
  AUTHOR = {Grolmusz, Vince},
  TITLE = {On multi-party communication complexity of random functions},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-93-162},
  MONTH = {December},
  YEAR = {1993},
  ISSN = {0946-011X},