Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR12-179 | 1st July 2013 18:00

Towards a Reverse Newman's Theorem in Interactive Information Complexity

RSS-Feed




Revision #2
Authors: Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman, Nikolay Vereshchagin
Accepted on: 1st July 2013 18:00
Downloads: 1034
Keywords: 


Abstract:

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.



Changes to previous version:

Forgot to fix the author list.


Revision #1 to TR12-179 | 1st July 2013 17:47

Towards a Reverse Newman's Theorem in Interactive Information Complexity





Revision #1
Authors: Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman, Nikolay Vereshchagin
Accepted on: 1st July 2013 17:47
Downloads: 705
Keywords: 


Abstract:

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.



Changes to previous version:

Paper is now full journal version. Numerous fixes, improvements and additions.


Paper:

TR12-179 | 13th December 2012 14:27

Towards a Reverse Newman's Theorem in Interactive Information Complexity





TR12-179
Authors: Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman
Publication: 21st December 2012 14:25
Downloads: 1959
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint