Počet záznamů: 1  

On the role of shared randomness in simultaneous communication

  1. 1.
    0434098 - MÚ 2015 RIV DE eng C - Konferenční příspěvek (zahraniční konf.)
    Bavarian, M. - Gavinsky, Dmitry - Ito, T.
    On the role of shared randomness in simultaneous communication.
    Automata, Languages, and Programming. Berlin: Springer, 2014 - (Esparza, J.; Fraigniaud, P.; Husfeldt, T.; Koutsoupias, E.), s. 150-162. Lecture Notes in Computer Science, 8572. ISBN 978-3-662-43947-0.
    [41st International Colloquium, ICALP 2014. Copenhagen (DK), 08.07.2014-11.07.2014]
    Grant CEP: GA ČR GBP202/12/G061
    Institucionální podpora: RVO:67985840
    Klíčová slova: automata theory * communication complexity * computational problem
    Kód oboru RIV: BA - Obecná matematika
    http://link.springer.com/chapter/10.1007%2F978-3-662-43948-7_13

    Suppose two parties who are interested in performing certain distributed computational tasks are given access to a source of correlated random bits ρ. This source of correlated randomness could be quite useful to the parties for solving various distributed computational problems as it enables the parties to act in a correlated manner. In this work, we initiate the study of power of different sources of shared randomness ρ in the setting of communication complexity; we shall do so in the model of simultaneous message passing (SMP) model of communication complexity, and we shall also argue that this model is the appropriate choice among the commonly studied models of two-party communication complexity for the purpose of studying shared randomness as a resource. As such, we introduce a natural measure for the strength of the correlation provided by a bipartite distribution that we call collision complexity.
    Trvalý link: http://hdl.handle.net/11104/0238238

     
    Název souboruStaženoVelikostKomentářVerzePřístup
    Gavinsky.pdf1242.1 KBVydavatelský postprintvyžádat
     
Počet záznamů: 1  

  Tyto stránky využívají soubory cookies, které usnadňují jejich prohlížení. Další informace o tom jak používáme cookies.