Project 3: the log-rank conjecture

The log-rank conjecture is one of my favorite open problems in complexity and combinatorics. At a high level it is asking “what is the structure of low-rank boolean matrices ?”. I will describe it and some equivalent formulations below, and then pose some more open-ended questions about low rank matrices with “combinatorial” structure.

Definitions and formulation

A boolean matrix is a matrix with 0,1 entries. A matrix is monochromatic if all its entries are the same. Given a matrix A, we denote by |A| the number of its entries. A rectangle (equivalently sub-matrix) B of A is a restriction of A to some subsets of rows and columns.

Log-rank conjecture: Let A be a boolean matrix. Assume the rank of A over the reals is r. Then there is a monochromatic rectangle  B in A of size |B| \ge |A| / 2^{(\log r)^k} for some absolute constant k>0.

If we replace rank over the reals with rank over other fields (such as \mathbb{F}_2) then the log-rank conjecture is false. The Hadamard matrix is one such counter-example, as its rank over  \mathbb{F}_2 is exponentially smaller than its rank over the reals. Over large enough finite fields, the analogous conjecture is equivalent to the conjecture over the reals. An interesting question is what is the threshold needed on the field size for this to hold; is it polynomial or exponential in the size of A?

History and connections to communication complexity

The log-rank conjecture is attributed to Lovász and Saks [LS88], where it was motivated by questions in communication complexity. Related conjectures were made by van Nuffelen [vN76] and Fajtlowicz [Faj88], motivated by questions in graph theory.

The original formulation of the log-rank conjecture is in terms of the deterministic communication complexity of A. A deterministic protocol for A with c bits is an iterative procedure, where at each iteration either the row or the columns of A are partitioned into two parts. At the end, we partition A to monochromatic rectangles. Clearly, if the deterministic communication complexity of A is c, then there is a monochromatic rectangle in A of size \ge |A| / 2^c. The reverse direction, showing that it suffices to find one large monochromatic rectangle in a low-rank boolean matrix in order to recurse and find a partition, was shown by Nisan and Wigderson [NW94]. The following is an equivalent formulation for the log-rank conjecture.

Log-rank conjecture (original formulation): Let A be a boolean matrix. Assume the rank of A over the reals is r. Then the deterministic communication complexity of A is at most (\log r)^k for some absolute constant k>0.

Known bounds

Let A be a boolean matrix of rank r. It can have at most 2^r distinct rows (and columns). To see why, assume that its columns space is spanned by the first r columns (permute the columns if this is not the case). Then the first r bits in a row specify the entire row. In particular, this shows that A has a monochromatic rectangle of size \ge |A| / 2^r, which is exponentially worse than the conjectured bound.

The best known upper bound is by Lovett [Lov16], and shows that there is a monochromatic rectangle of size \ge |A| / r^{O(\sqrt{r})}. The best lower bound is by Göös, Pitassi and Watson [GPW18], who showed that k \ge 2 is needed in the log-rank conjecture formulation above.

Special cases

There are two special cases which are natural from the communication complexity perspective, that show connections between the log-rank conjecture and boolean function analysis. They are related to “lifted functions”, and specifically are XOR-functions and AND-functions. Below let f:\{0,1\}^n \to \{0,1\} be an arbitrary boolean function.

XOR functions: The corresponding XOR-function for f is the 2^n \times 2^n matrix A_{x,y} = f(x \oplus y), where \oplus is an entry-wise XOR. The log-rank conjecture for XOR-functions has an appealing equivalent form in terms of the boolean function f. First, it turns out that the rank of A is equal to the Fourier sparsity of f, namely the number of nonzero Fourier coefficients of f. Tsang, Wong, Xie, Zhang [TWXZ13] suggested the following conjecture, and shows that it implies the log-rank conjecture for XOR functions. Later, Hatami, Hosseini and Lovett [HHL18] showed that the two conjectures are equivalent. Below we identify \{0,1\}^n with the linear space \mathbb{F}_2^n.

Log-rank conjecture for XOR functions (equivalent formulation): Let f:\{0,1\}^n \to \{0,1\} be a boolean function. Assume that the Fourier sparsity of f is r. Then there is a subspace V \subset \mathbb{F}_2^n on which f is constant, where the co-dimension of V is (\log r)^k for some absolute constant k>0.

AND functions: The corresponding AND-function for f is the 2^n \times 2^n matrix A_{x,y} = f(x \wedge y), where \wedge is an entry-wise AND. The rank of A is equal to the sparsity of f as a polynomial. Namely, the number of nonzero coefficients when expressing f as a linear combination of monomials \prod_{i \in S} x_i for S \subseteq [n]. The following conjecture is the natural analog of the log-rank conjecture for XOR functions. We don’t know if it is equivalent to the log-rank conjecture for AND functions, but it seems believable. Below, a subcube C \subset \{0,1\}^n is obtained by fixing some inputs to constants; it’s co-dimension is the number of fixed inputs.

Log-rank conjecture for AND functions (possibly equivalent formulation): Let f:\{0,1\}^n \to \{0,1\} be a boolean function. Assume that the polynomial sparsity of f is r. Then there is a subcube C \subset \{0,1\}^n on which f is constant, where the co-dimension of C is (\log r)^k for some absolute constant k>0.

Other communication complexity models

Analogs of the log-rank conjecture have been suggested for other models of communication complexity, such as randomized communication or quantum communication. In a recent breakthrough, Chattopadhyay, Mande, and Sherif [CMS19] disproved the relevant log-rank conjecture for randomized communication, and suggested a more refined variant that may be true. Please see their paper for details, as well as [ABT19, SdW19] for an extension to the quantum case.

Structure of low-rank matrices

A more general question is what is the structure of low-rank matrices with some “combinatorial” structure. The log-rank conjecture fixes one such structure – having boolean entries. Here is another conjecture, where we replace “boolean” with “sparse”.

Sparse low-rank conjecture: let A be matrix, where a constant fraction of its entries are zero. Then there is a rectangle B in A, where all the entries are zero, of size |B| \ge |A| / 2^{O(\sqrt{r})}.

The bound in the conjecture, if true, is best possible. This conjecture has connections to matrix rigidity and to additive combinatorics. You can read more about it in a survey I wrote a few years ago on progress on the log-rank conjecture [Lov14]. Note that it is missing some recent developments (eg [GPW18], [CMS19]).

In general, I think that studying questions in the intersection of algebra (e.g. low rank) and combinatorics (e.g. boolean, sparse) leads to both interesting questions, which potentially can connect various fields in TCS and math. To some extent, the entire field of additive / arithmetic combinatorics can be seen in this way.

Exact quantum vs deterministic communication protocols

(this information is from Ronald De-Wolf)

A corollary of the log-rank conjecture is that for boolean communication problems, exact quantum protocols (quantum protocols without errors) are equivalent to deterministic protocols, up to polynomial factors.

For quantum protocols without entanglement, this follows from the log-rank conjecture since it is known that an exact quantum protocol with c bits implies that the communication matrix has rank at most 2^c. For quantum protocols with entanglement this is more involved and was proved by Buhrman and De-Wolf [BdW01].

The question of whether the sampling analog of exact quantum and deterministic protocols is equivalent is in fact equivalent to the log-rank conjecture. This is given as Conjecture 2 in [T99] and is shown in [ASTVW03].

Bibliography

[ABT19] A. Anshu, G. Boddu and D. Touchette. Quantum Log-Approximate-Rank conjecture is also false. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS).

[ASTVW03] Ambainis, A., Schulman, L. J., Ta-Shma, A., Vazirani, U., & Wigderson, A. (2003). The quantum communication complexity of sampling. SIAM Journal on Computing, 32(6), 1570-1585.

[BdW01] Buhrman, Harry, and Ronald de Wolf. Communication complexity lower bounds by polynomials. Proceedings 16th Annual IEEE Conference on Computational Complexity. IEEE, 2001.

[CMS19] A. Chattopadhyay, N.S. Mande, and S. Sherif. The log-approximate-rank conjecture is false. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing. 2019.

[Faj88] S. Fajtlowicz. On conjectures of graffiti. Discrete mathematics, 72(1):113–118, 1988.

[GPW18] M. Göös, T. Pitassi, and T. Watson. Deterministic communication vs. partition number. SIAM Journal on Computing 47.6 (2018): 2435-2450.

[HHL18] H. Hatami, K. Hosseini and S. Lovett. Structure of protocols for XOR functions. SIAM Journal on Computing 47.1 (2018): 208-217.

[Lov14] S. Lovett. Recent advances on the log-rank conjecture in communication complexity. Bulletin of EATCS 1.112 (2014).

[Lov16] S. Lovett. Communication is bounded by root of rank. Journal of the ACM (JACM) 63.1 (2016): 1-9.

[LS88] L. Lovász and M. Saks. Lattices, Möbius Functions and Communication Complexity. Annual Symposium on Foundations of Computer Science, pages 81–90, 1988.

[NW94] N. Nisan and A. Wigderson. On Rank vs. Communication Complexity. Proceedings of the 35rd Annual Symposium on Foundations of Computer Science, pages 831–836, 1994.

[SdW19] M. Sinha and R. de Wolf. Exponential separation between quantum communication and logarithm of approximate rank. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS).

[T99] Amnon Ta-Shma. Classical versus Quantum Communication Complexity. SIGACT News, Complexity Theory Column 23, 1999.

[TWXZ13] H. Y. Tsang, C. H. Wong, N. Xie and S. Zhang. Fourier sparsity, spectral norm, and the log-rank conjecture. 2013 IEEE 54th Annual Symposium on Foundations of Computer Science.

[vN76] C. van Nuffelen. A bound for the chromatic number of a graph. American Mathematical Monthly, pages 265–266, 1976.