Towards a reverse Newman's theorem in interactive information complexity

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F13%3A00422288" target="_blank" >RIV/67985840:_____/13:00422288 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1109/CCC.2013.12" target="_blank" >http://dx.doi.org/10.1109/CCC.2013.12</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/CCC.2013.12" target="_blank" >10.1109/CCC.2013.12</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Towards a reverse Newman's theorem in interactive information complexity

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Towards a reverse Newman's theorem in interactive information complexity

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2013

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

IEEE Conference on Computational Complexity 2013

ISBN

978-1-4673-6466-9

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

24-33

Název nakladatele

IEEE

Místo vydání

Washington

Místo konání akce

Palo Alto

Datum konání akce

5. 6. 2013

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—