de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

A communication-randomness tradeoff for two-processor systems

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44431

Fleischer,  Rudolf
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Fleischer, R., Jung, H., & Mehlhorn, K. (1995). A communication-randomness tradeoff for two-processor systems. Information and Computation, 116, 155-161.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-AC3E-C
Abstract
We present a tight tradeoff between the expected communication complexity $\bar{C}$ (for a two-processor system) and the number $R$ of random bits used by any Las Vegas protocol for the list-nondisjointness function of two lists of $n$ numbers of $n$ bits each. This function evaluates to $1$ if and only if the two lists correspond in at least one position. We show a $\log(n^2/\bar{C})$ lower bound on the number of random bits used by any Las Vegas protocol, $\Omega(n)\le\bar{C}\le O(n^2)$. We also show that expected communication complexity $\bar{C}$, $\Omega(n\log n) \le\bar{C}\le O(n^2)$, can be achieved using no more than $\log(n^2/\bar{C}) + \lceil\log(2+\log(n^2/\bar{C}))\rceil+6$ random bits.", xxx-references = "STOC::AhoUY83, FOCS::CanettiG90, STOC::Furer87, STOC::HalstenbergR88, STOC::KrizancPU88, FOCS::LovaszS88, STOC::MehlhornS82, STOC::PapadimitriouS82, FOCS::Yao77, STOC::Yao79, FOCS::Yao83", references = "\cite{STOC::AhoUY1983} \cite{FOCS::CanettiG1990} \cite{STOC::Furer1987} \cite{STOC::HalstenbergR1988} \cite{STOC::KrizancPU1988} \cite{FOCS::LovaszS1988} \cite{STOC::MehlhornS1982} \cite{STOC::PapadimitriouS1982} \cite{FOCS::Yao1977} \cite{STOC::Yao1979} \cite{FOCS::Yao1983}