On multi-party communication complexity of random functions

Grolmusz, Vince

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Report

On multi-party communication complexity of random functions

MPS-Authors

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

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: https://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.