Open Collections

Description

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)