Open Collections

The Log-Approximate-Rank Conjecture is False

Banff International Research Station for Mathematical Innovation and Discovery

We construct a simple and total XOR function F on 2n variables that has only O(n) spectral norm, O(n^2) approximate rank and O(n^{2.5}) approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of Omega(sqrt(n)). This yields the first exponential gap between the logarithm of the approximate rank and randomized communication complexity for total functions. Thus, F witnesses a refutation of the Log-Approximate-Rank Conjecture which was posed by Lee and Shraibman (2007) as a very natural analogue for randomized communication of the still unresolved Log-Rank Conjecture for deterministic communication. The best known previous gap for any total function between the two measures was a recent 4th-power separation by Göös, Jayram, Pitassi and Watson (2017). Remarkably, after our manuscript was published in the public domain, two groups of researchers, Anshu-Boddu-Touchette (2018) and Sinha-de-Wolf (2018), showed independently that the function F even refutes the Quantum-Log-Approximate-Rank Conjecture. (Joint work with Nikhil Mande and Suhail Sherif)

Mathematics; Computer science; Theoretical computer science

video/mp4

Author affiliation: Tata Institute of Fundamental Research

2020-01-08

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/73201

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/