The Log-Approximate-Rank Conjecture Is False
- 21 June 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 67 (4), 1-28
- https://doi.org/10.1145/3396695
Abstract
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 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 that 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öös et al. Additionally, our function F refutes Grolmusz’s conjecture and a variant of the log-approximate-nonnegative-rank conjecture suggested recently by Kol et al., both of which are implied by the log-approximate-rank conjecture. The complement of F has exponentially large approximate nonnegative rank. This answers a question of Lee [32], showing that approximate nonnegative rank can be exponentially larger than approximate rank. The inner function F also falsifies a conjecture about parity measures of Boolean functions made by Tsang et al. The latter conjecture implied the log-rank conjecture for XOR functions. We are pleased to note that shortly after we published our results, two independent groups of researchers, Anshu et al. and Sinha and de Wolf, used our function F to prove that the quantum-log-rank conjecture is also false by showing that F has Ω(n1/6) quantum communication complexity.Keywords
Funding Information
- Department of Atomic Energy, Government of India (12-R8D-TFR-5.01-0500)
- DAE fellowship
This publication has 39 references indexed in Scilit:
- A note on the query complexity of the Condorcet winner problemInformation Processing Letters, 2008
- Lower Bounds in Communication ComplexityFoundations and Trends® in Theoretical Computer Science, 2007
- Quantum communication complexity of symmetric predicatesIzvestiya: Mathematics, 2003
- On the power of circuits with gates of low L1 normsTheoretical Computer Science, 1997
- Geometric arguments yield better bounds for threshold circuits and distributed computingTheoretical Computer Science, 1996
- On the distributional complexity of disjointnessTheoretical Computer Science, 1992
- Expressing combinatorial optimization problems by Linear ProgramsJournal of Computer and System Sciences, 1991
- Private vs. common random bits in communication complexityInformation Processing Letters, 1991
- Learning decision trees from random examplesInformation and Computation, 1989
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963