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

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>

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
—

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

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

Similar results(10)