ECCC-Report TR18-176https://eccc.weizmann.ac.il/report/2018/176Comments and Revisions published for TR18-176en-usSat, 27 Oct 2018 00:41:29 +0300
Paper TR18-176
| The Log-Approximate-Rank Conjecture is False |
Arkadev Chattopadhyay,
Nikhil Mande,
Suhail Sherif
https://eccc.weizmann.ac.il/report/2018/176We 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.Sat, 27 Oct 2018 00:41:29 +0300https://eccc.weizmann.ac.il/report/2018/176