Number of the records: 1
Towards a reverse Newman’s theorem in interactive information complexity
- 1.
SYSNO ASEP 0465743 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve WOS Title Towards a reverse Newman’s theorem in interactive information complexity Author(s) Brody, J. (DK)
Buhrman, H. (NL)
Koucký, Michal (MU-W) RID, SAI, ORCID
Loff, B. (NL)
Speelman, F. (NL)
Vereshchagin, N.K. (RU)Source Title Algorithmica. - : Springer - ISSN 0178-4617
Roč. 76, č. 3 (2016), s. 749-781Number of pages 33 s. Language eng - English Country US - United States Keywords communication complexity ; information complexity ; information theory Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) Institutional support MU-W - RVO:67985840 UT WOS 000384564100007 EID SCOPUS 84954306921 DOI 10.1007/s00453-015-0112-9 Annotation 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. Workplace Mathematical Institute Contact Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Year of Publishing 2017
Number of the records: 1