Randomised Individual Communication Complexity
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F08%3A00318526" target="_blank" >RIV/67985840:_____/08:00318526 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Randomised Individual Communication Complexity
Original language description
In this paper we study the individual communication complexity of the following problem. Alice receives an input string x and Bob an input string y, and Alice has to output y. For deterministic protocols it has been shown Buhrman et al. that C(y) many bits need to be exchanged even if the actual amount of information C(y) | x) is much smaller than C(y). It turns out that for randomised protocols the situation is very different. We establish randomised protocols whose communication complexity is close tothe information theoretical lower bound. We furthermore initiate and obtain results about the randomised round comlexity of this problem and show trade-offs between the amount of communication and the number of rounds. In order to do this we establish ageneral framework for studying these types of questions
Czech name
Pravděpodobnostní individuální komunikační složitosti
Czech description
Studujeme pravděpodobnostní individuální komunikační složitost identity.
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GP201%2F07%2FP276" target="_blank" >GP201/07/P276: Computational and communication complexity of Boolean functions, and derandomization</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2008
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Proceedings of IEEE Conference on Computational Complexity 2008
ISBN
978-0-7695-3169-4
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
—
Publisher name
IEEE Computer Society Press
Place of publication
Maryland
Event location
College Park
Event date
Jun 23, 2008
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000257941800031