The Log-Approximate-Rank Conjecture Is False
Arkadev Chattopadhyay, Nikhil S. Mande, Suhail Sherif · Journal of the ACM · 2019
We construct a simple and total XOR function F on 2n variables that has only O(√n) spectral norm, O(n2) approximate rank and O(n2.5) approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of Ω(√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 (LARC) which was posed by Lee and Shraibman 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 is a recent 4th-power separation by G'o'os, Jayram, Pitassi and Watson.