Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-176 | 26th October 2018 22:33

The Log-Approximate-Rank Conjecture is False



We construct a simple and total XOR function $F$ on $2n$ variables that has only $O(\sqrt{n})$ spectral norm, $O(n^2)$ approximate rank and $n^{O(\log n)}$ 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 (LARC) which was posed by Lee and Shraibman [LS09] 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öös, Jayram, Pitassi and Watson [GJPW17].

Additionally, our function $F$ refutes Grolmusz's Conjecture [Gro97] and a variant of the Log-Approximate-Nonnegative-Rank Conjecture, suggested recently by Kol, Moran, Shpilka and Yehudayoff [KMSY14], both of which are implied by the LARC. The complement of $F$ has exponentially large approximate nonnegative rank. This answers a question of Lee [Lee12] and Kol et al. [KMSY14], showing that approximate nonnegative rank can be exponentially larger than approximate rank. The function $F$ also falsifies a conjecture about parity measures of Boolean functions made by Tsang, Wong, Xie and Zhang [TWXZ13]. The latter conjecture implied the Log-Rank Conjecture for XOR functions. Our result further implies that at least one of the following statements is true: (a) The Quantum-Log-Rank Conjecture is false; (b) The total function $F$ exponentially separates quantum communication complexity from its classical randomized counterpart.

ISSN 1433-8092 | Imprint