Number of the records: 1
Towards a reverse Newman's theorem in interactive information complexity
- 1.
SYSNO ASEP 0422288 Document Type C - Proceedings Paper (int. conf.) R&D Document Type Conference Paper 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 IEEE Conference on Computational Complexity 2013. - Washington : IEEE, 2013 - ISBN 978-1-4673-6466-9 Pages s. 24-33 Number of pages 10 s. Publication form Print - P Action IEEE Conference on Computational Complexity 2013 Event date 05.06.2013-07.06.2013 VEvent location Palo Alto Country US - United States Event type WRD Language eng - English Country US - United States Keywords comlexity theory ; communication complexity ; interactive information complexity Subject RIV BA - General Mathematics R&D Projects IAA100190902 GA AV ČR - Academy of Sciences of the Czech Republic (AV ČR) GBP202/12/G061 GA ČR - Czech Science Foundation (CSF) Institutional support MU-W - RVO:67985840 UT WOS 000332541200004 EID SCOPUS 84885615207 DOI 10.1109/CCC.2013.12 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 only 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. 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 2014
Number of the records: 1