The Log-Approximate-Rank Conjecture Is False

We construct a simple and total Boolean function F = f XOR 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 polyno...