Number of the records: 1  

Towards a reverse Newman’s theorem in interactive information complexity

  1. 1.
    0465743 - MÚ 2017 RIV US eng J - Journal Article
    Brody, J. - Buhrman, H. - Koucký, Michal - Loff, B. - Speelman, F. - Vereshchagin, N.K.
    Towards a reverse Newman’s theorem in interactive information complexity.
    Algorithmica. Roč. 76, č. 3 (2016), s. 749-781. ISSN 0178-4617. E-ISSN 1432-0541
    R&D Projects: GA AV ČR IAA100190902
    Institutional support: RVO:67985840
    Keywords : communication complexity * information complexity * information theory
    Subject RIV: BA - General Mathematics
    Impact factor: 0.735, year: 2016

    Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with but a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct-sum theorems through the compression of interactive communication in the bounded-round setting. To obtain this application, we prove a new one-shot variant of the Slepian–Wolf coding theorem, interesting in its own right. Furthermore, we show that if a Reverse Newman’s Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.
    Permanent Link:

    Koucky.pdf4630.8 KBPublisher’s postprintrequire
Number of the records: 1  

  This site uses cookies to make them easier to browse. Learn more about how we use cookies.