Pravděpodobnostní individuální komunikační složitosti

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Randomised Individual Communication Complexity

Popis výsledku v původním jazyce

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

Název v anglickém jazyce

Randomised Individual Communication Complexity

Popis výsledku anglicky

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

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GP201%2F07%2FP276" target="_blank" >GP201/07/P276: Výpočetní a komunikační složitost Booleovských funkcí a derandomizace</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2008

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Proceedings of IEEE Conference on Computational Complexity 2008

ISBN

978-0-7695-3169-4

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

—

Název nakladatele

IEEE Computer Society Press

Místo vydání

Maryland

Místo konání akce

College Park

Datum konání akce

23. 6. 2008

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000257941800031