Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR13-080 | 4th June 2013 06:28

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


Authors: Dmitry Gavinsky, Shachar Lovett
Publication: 4th June 2013 15:40
Downloads: 1913


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