En route to the log-rank conjecture: new reductions and equivalent formulations

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F14%3A00434135" target="_blank" >RIV/67985840:_____/14:00434135 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-662-43948-7_43" target="_blank" >http://dx.doi.org/10.1007/978-3-662-43948-7_43</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-662-43948-7_43" target="_blank" >10.1007/978-3-662-43948-7_43</a>

Jazyk výsledku

angličtina

Název v původním jazyce

En route to the log-rank conjecture: new reductions and equivalent formulations

Popis výsledku v původním jazyce

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that low-rank matrices have efficient protocols in any of the aforementioned measures. Furthermore, we show that the notion of zero-communication complexity is equivalent to an extension of the common discrepancy bound. Linial et al. [Combinatorica, 2007] showed that the discrepancy of a sign matrix is lower-bounded by an inverse polynomial in the logarithm of the associated matrix. We show that if these results can be generalized to the extended discrepancy, this will imply the log-rank conjecture.

Název v anglickém jazyce

En route to the log-rank conjecture: new reductions and equivalent formulations

Popis výsledku anglicky

We prove that several measures in communication complexity are equivalent, up to polynomial factors in the logarithm of the rank of the associated matrix: deterministic communication complexity, randomized communication complexity, information cost and zero-communication cost. This shows that in order to prove the log-rank conjecture, it suffices to show that low-rank matrices have efficient protocols in any of the aforementioned measures. Furthermore, we show that the notion of zero-communication complexity is equivalent to an extension of the common discrepancy bound. Linial et al. [Combinatorica, 2007] showed that the discrepancy of a sign matrix is lower-bounded by an inverse polynomial in the logarithm of the associated matrix. We show that if these results can be generalized to the extended discrepancy, this will imply the log-rank conjecture.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2014

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

Automata, Languages, and Programming

ISBN

978-3-662-43947-0

ISSN

—

e-ISSN

—

Počet stran výsledku

11

Strana od-do

514-524

Název nakladatele

Springer

Místo vydání

Berlin

Místo konání akce

Copenhagen

Datum konání akce

8. 7. 2014

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

WRD - Celosvětová akce

Kód UT WoS článku

000352643300045