Arkadev Chattopadhyay: The Log-Approximate-Rank Conjecture is False

Abstract: 

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).

Additionally, our function F refutes Grolmusz's Conjecture (1997) and a variant of the
Log-Approximate-Nonnegative-Rank Conjecture, suggested by Kol, Moran, Shpilka and
Yehudayoff (2014), both of which are implied by the LARC. The complement of F has
exponentially large approximate nonnegative rank. This answers a question of Lee (2012)
and Kol et al. (2014), 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 (2013). The latter
conjecture implied the Log-Rank Conjecture for XOR functions.

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.

(This is joint work with Nikhil Mande and Suhail Sherif)