Number of the records: 1
Towards a reverse Newman's theorem in interactive information complexity
- 1.0422288 - MÚ 2014 RIV US eng C - Conference Paper (international conference)
Brody, J. - Buhrman, H. - Koucký, Michal - Loff, B. - Speelman, F. - Vereshchagin, N.K.
Towards a reverse Newman's theorem in interactive information complexity.
IEEE Conference on Computational Complexity 2013. Washington: IEEE, 2013, s. 24-33. ISBN 978-1-4673-6466-9.
[IEEE Conference on Computational Complexity 2013. Palo Alto (US), 05.06.2013-07.06.2013]
R&D Projects: GA AV ČR IAA100190902; GA ČR GBP202/12/G061
Institutional support: RVO:67985840
Keywords : comlexity theory * communication complexity * interactive information complexity
Subject RIV: BA - General Mathematics
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=6597746
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.
Permanent Link: http://hdl.handle.net/11104/0228474
File Download Size Commentary Version Access Koucky1.pdf 1 260.9 KB Publisher’s postprint require
Number of the records: 1