Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:








Author, Editor(s)

Author(s):

Fleischer, Rudolf
Jung, Hermann
Mehlhorn, Kurt

dblp
dblp
dblp



BibTeX cite key*:

Fleischer-Jung-Mehlhorn95

Title

Title*:

A communication-randomness tradeoff for two-processor systems

Journal

Journal Title*:

Information and Computation

Journal's URL:


Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

Academic Press

Publisher's URL:


Publisher's
Address:


ISSN:

0890-5401

Vol, No, pp, Date

Volume*:

116

Number:

2

Publishing Date:

1995

Pages*:

155-161

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:


Note, Abstract, ©

Note:


(LaTeX) 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}

URL for the Abstract:


Categories,
Keywords:


HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Public

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

Expert

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat


BibTeX Entry:

@ARTICLE{Fleischer-Jung-Mehlhorn95,
AUTHOR = {Fleischer, Rudolf and Jung, Hermann and Mehlhorn, Kurt},
TITLE = {A communication-randomness tradeoff for two-processor systems},
JOURNAL = {Information and Computation},
PUBLISHER = {Academic Press},
YEAR = {1995},
NUMBER = {2},
VOLUME = {116},
PAGES = {155--161},
ISBN = {0890-5401},
}


Entry last modified by Christine Kiesel, 03/02/2010
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Evelyn Haak
Created
03/14/1997 11:34:27 AM
Revisions
3.
2.
1.
0.
Editor(s)
Christine Kiesel
Evelyn Haak
Uwe Brahm
Evelyn Haak
Edit Dates
23.08.2006 12:03:05
20/03/97 15:58:02
20/03/97 11:49:34
14/03/97 11:35:59
Show details for Attachment SectionAttachment Section
Hide details for Attachment SectionAttachment Section