de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Impressum Kontakt Einloggen
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Bericht

On multi-party communication complexity of random functions

MPG-Autoren

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)

MPI-I-93-162.pdf
(beliebiger Volltext), 7MB

Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0014-B775-6
Zusammenfassung
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.