En route to the log-rank conjecture: new reductions and equivalent formulations
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
En route to the log-rank conjecture: new reductions and equivalent formulations
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2014
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Automata, Languages, and Programming
ISBN
978-3-662-43947-0
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
514-524
Publisher name
Springer
Place of publication
Berlin
Event location
Copenhagen
Event date
Jul 8, 2014
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
000352643300045