ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-080 | 4th June 2013 06:28

En Route to the log-rank Conjecture: New Reductions and Equivalent Formulations

RSS-Feed




TR13-080
Authors: Dmitry Gavinsky, Shachar Lovett
Publication: 4th June 2013 15:40
Downloads: 1591
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint