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 for some absolute constant k>0.
If we replace rank over the reals with rank over other fields (such as ) then the log-rank conjecture is false. The Hadamard matrix is one such counter-example, as its rank overΒ 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 . 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 for some absolute constant k>0.
Known bounds
Let A be a boolean matrix of rank r. It can have at most 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 , 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 . The best lower bound is by GΓΆΓΆs, Pitassi and Watson [GPW18], who showed that 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 be an arbitrary boolean function.
XOR functions: The corresponding XOR-function for f is the matrix , where 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 with the linear space .
Log-rank conjecture for XOR functions (equivalent formulation): Let be a boolean function. Assume that the Fourier sparsity of f is r. Then there is a subspace on which f is constant, where the co-dimension of V is for some absolute constant k>0.
AND functions: The corresponding AND-function for f is the matrix , where 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 for . 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 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 be a boolean function. Assume that the polynomial sparsity of f is r. Then there is a subcube on which f is constant, where the co-dimension of C is 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 .
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 . 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.
PolyTCS 11:21 pm on December 6, 2020 Permalink | Log in to Reply
Dear all, please don’t freak out by the famous log-rank conjecture. π As request by some participants, Professor Lovett kindly gave an online tutorial and updated the proposal with several more approachable subproblems. You may find this survey paper helpful to get more background on this problem: Lokam, Satya. Complexity lower bounds using linear algebra. Now Publishers Inc, 2009. http://www.cs.toronto.edu/~toni/Courses/CommComplexity/Papers/lokam-book.pdf
LikeLike
domotorp 9:34 am on January 29, 2021 Permalink | Log in to Reply
Let me link here to this recent paper on this topic: https://arxiv.org/abs/2101.09592
LikeLike
nathantemple2014 8:05 am on December 12, 2021 Permalink | Log in to Reply
Hello, thank you for posting this fascinating problem. Does the “absolute constant k>0” in the conjecture refer to a constant good for any Boolean matrix A whatsoever?
LikeLike
shacharlovett 10:01 am on December 12, 2021 Permalink | Log in to Reply
yes, this is true
LikeLike
nathantemple2014 7:38 am on December 13, 2021 Permalink | Log in to Reply
Is there an algorithm known that, given a square boolean matrix M computes the size of the largest monochromatic rectangle?
There are algorithms for computing the largest *contiguous* monochromatic rectangles, but to compute the largest non-contiguous rectangles it would need to “shuffle” the rows and columns so that the rectangles become contiguous.
In this document (https://www.cs.princeton.edu/courses/archive/spring05/cos598B/commcomplexity1.pdf) in exercise 12 near the bottom, it states that it’s not known whether a closely related problem has an algorithm in EXPTIME. Is that still current?
Thanks,
LikeLike
nathantemple2014 8:21 am on December 14, 2021 Permalink | Log in to Reply
Hi, what does the conjecture say when r=1? It would seem to say |B|>=|A|, but there are counterexamples to this. There are matrices of rank 1 that do not have a monochromatic rectangle that makes up the whole matrix.
LikeLike
shacharlovett 8:04 pm on December 14, 2021 Permalink | Log in to Reply
For your first question, the exercise there is to show that the problem is in EXPTIME. Basically, this is the complexity of full enumeration.
For your second question, for r=1 you have a monochromatic matrix that makes up a constant fraction of the matrix. In general I was avoiding adding constants, but if you want to be precise then replace r with O(r)
LikeLiked by 1 person
nathantemple2014 3:54 pm on December 15, 2021 Permalink | Log in to Reply
Hello, is there any way to type in Latex in these comment boxes?
LikeLike
nathantemple2014 3:55 pm on December 15, 2021 Permalink | Log in to Reply
LikeLike
nathantemple2014 3:56 pm on December 15, 2021 Permalink
nvm, got my answer!
LikeLike
nathant201 12:26 am on December 21, 2021 Permalink | Log in to Reply
Should the bound
be
or
?
It seems the reasoning was leading up to that. If the rows can be partitioned into blocks of size at most , then at least 1 row can be repeated times, and there is at least 1 row in each block with at least 0’s or 1’s, so there is a monochromatic rectangle of at least
?
LikeLike
nathant201 12:09 am on December 22, 2021 Permalink | Log in to Reply
Can you please outline the proof for “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”?
LikeLike
nathant201 9:37 pm on December 25, 2021 Permalink | Log in to Reply
It seems we need to already know the log-rank conjecture is true to go from monochromatic rectangles to a bound on the complexity of f? That is, if the log-rank conjecture is true, and we know the size of a monochromatic rectangle in a matrix M(f), then we can bound the deterministic complexity of f?
LikeLike