Log-rank conjecture
Is the number of bits two parties must exchange to compute a Boolean function bounded by a polynomial in the logarithm of its matrix rank?
Summary
Why it is open
In two-party communication, one party holds x, the other y, and they exchange bits to compute f(x, y); the deterministic communication complexity of f is the number of bits an optimal deterministic protocol sends [3]. The values of f form a matrix M_f with a row for each x and a column for each y. Kurt Mehlhorn and Erik M. Schmidt observed in 1982 that a protocol sending c bits splits M_f into at most 2^c rectangles (sets of rows times sets of columns) on which f is constant; each has rank at most one, so the communication is at least log rank(f) [3, 10].
Lovász and Saks conjectured in 1988 that this bound is tight up to polynomial factors: there is a constant C such that the communication is at most C(log rank(f))^C for every Boolean function f [1, 3]. The simplest upper bound is rank(f) itself, exponentially weaker [3]. As of October 2026 the best proved bound is still of the order of the square root of the rank [9, 12], exponentially far from the conjecture [10].
The conjecture has equivalent forms outside communication complexity. In graph theory, it asks whether the logarithm of a graph's chromatic number (the fewest colours needed so that adjacent vertices differ) is bounded by a polynomial in the logarithm of the rank of its adjacency matrix; an essentially equivalent conjecture was given by Cyriel van Nuffelen in 1976 and by Siemion Fajtlowicz [3, 11]. In linear algebra, it asks whether the rank of a 0–1 matrix and its partition number, the fewest all-1 submatrices that partition its 1-entries, are quasi-polynomially related [11].
A resolution would be a proof for every Boolean function, or functions whose communication outgrows every fixed power of log rank. No prize or committee sets further terms; the status here follows Wikipedia's list of unsolved problems in computer science [13].
What is known
Gaps (1994–2026). A sequence of constructions ending in an unpublished example of Eyal Kushilevitz, reported by Noam Nisan and Avi Wigderson, gives functions whose communication is at least (log rank)^(log₃ 6), so the constant C must be at least about 1.63 [3]. In 2015 Mika Göös, Toniann Pitassi and Thomas Watson found a function with communication Ω̃(log² rank), where Ω̃ hides polylogarithmic factors [5]. They adapted a simulation theorem of Ran Raz and Pierre McKenzie that turns lower bounds for query complexity, the number of input bits a decision tree reads, into communication lower bounds [5]; that paper, "Separation of the monotone NC hierarchy", is discussed on the Papex page NC versus P. Lianna Hambardzumyan, Shachar Lovett and Morgan Shirley cite a later construction by Kaspars Balodis, Shalev Ben-David, Göös, Siddhartha Jain and Robin Kothari as the largest known separation, with the logarithm of the partition number at least Ω(log² rank) [8, 11]. An August 2026 preprint by Zhao Song, not peer reviewed, says that such summaries suppress polylog(log r) factors, computes the explicit bound of Göös and colleagues as Ω((log r)²/(log log r)²), with r the rank, and claims Ω((log r)²/log log r) [12]. Song writes that "no superpolynomial-in-log r lower bound is known" [12].
Upper bounds (1994–2025). For graphs of rank r, Andrew Kotlov and Lovász bounded the chromatic number by 2^(r/2), and Kotlov by (4/3)^r [3]. Nisan and Wigderson showed that it is enough to find large monochromatic rectangles: if every Boolean matrix of rank r has one covering a 2^(−c(r)) fraction of its entries, there is a protocol of cost O(log² r + c(r) + c(r/2) + …) [3]. Lovett proved in 2013 (journal version 2016) that every Boolean function of rank r has a protocol of cost O(√r · log r), using the discrepancy of low-rank matrices, "a nearly quadratic improvement" on earlier bounds [4]. In 2023 Benny Sudakov and István Tomon removed the logarithm: every m × n binary matrix of rank at most r has an all-0 or all-1 submatrix of size (m·2^(−O(√r))) × (n·2^(−O(√r))), so the communication is O(√r) [9]. Dmitry Gavinsky and Lovett showed that a randomised protocol of cost c for f gives a deterministic one of cost O(c · log² rank(f)) [3].
Special classes and reformulations (2021–2026). For AND-functions, f(x ∧ y) with bit-wise AND, Alexander Knop, Lovett, Sam McGuire and Weiqiang Yuan proved the conjecture up to a factor of log n [7]. Hambardzumyan, Lovett and Shirley showed that every Boolean matrix of rank r is a sum of at most O(r log r) all-1 rectangles with signs ±1, which turns the conjecture into the question whether signed decompositions can be made positive with quasi-polynomial blow-up [11]. Gal Beniamini, Nati Linial and Adi Shraibman showed that graphs with small clique number whose complement has low rank ("Rank-Ramsey" graphs) yield separations in the graph form of the conjecture; they built such graphs with clique number at most 41 and complement rank O(n^(1−1/10000)), and with logarithmic clique number and complement rank about n^(2/3) [10].
Related conjectures. The Alon–Saks–Seymour conjecture, that a graph made of k edge-disjoint complete bipartite graphs has chromatic number at most k + 1, was disproved by Hao Huang and Sudakov in 2012 [2], and Balodis and colleagues gave a near-optimal answer to how far the chromatic number can exceed this number k, the biclique partition number [8]. The log-approximate-rank conjecture of Troy Lee and Shraibman, a randomised analogue, is false: Arkadev Chattopadhyay, Nikhil Mande and Suhail Sherif gave a function on 2n bits with approximate rank O(n²) and randomised communication Ω(√n) [6].
Main approaches
Large monochromatic rectangles. Find a big constant submatrix and recurse [3]. Strongest evidence: the O(√r) bound [9]. Main difficulty: Lovett notes that his bound seems tight for his proof technique, and that the relation between discrepancy and rank it uses is tight in general, for example for the inner product function [4]; Sudakov and Tomon's discrepancy bound is also "best possible" [9].
Simulating other protocols. Show that low-rank functions have cheap randomised, low-information or zero-communication protocols, which Gavinsky and Lovett convert into deterministic ones [3]. Strongest evidence: the O(c · log² rank) conversion [3]. Main difficulty: the conversion shows only that it would suffice to prove that every low-rank matrix has an efficient randomised protocol [3]; quantum protocols are a type that Gavinsky and Lovett could not analyse [3]; and the randomised analogue of the conjecture, stated with approximate rank, is false [6].
Restricted classes and lifting. Prove the conjecture for structured functions, often by relating communication to the complexity of a decision tree [5, 7]. Strongest evidence: AND-functions up to a log n factor, with no assumption on f [7]. Main difficulty: earlier special cases "needed significant restrictions on f such as monotonicity or low F2-degree" [7], and the log n factor remains [7].
Reformulation. Restate the conjecture through other matrix or graph parameters [10, 11]. Strongest evidence: the near-equivalence of rank and signed rectangle rank [11]. Main difficulty: a result of Lindström shows that O(r log r) is the limit of their proof technique, and what remains, they write, is "whether allowing cancellations is significantly stronger than monotonicity" [11].
Open sub-questions
- Beyond quadratic. Is there a family of Boolean matrices whose communication is at least (log rank)^(2+ε) for some ε > 0, beyond the near-quadratic gaps now known [5, 8, 12]?
- Below the square root. Does every Boolean matrix of rank r contain a monochromatic rectangle covering a 2^(−O(r^α)) fraction for some α < 1/2? By the Nisan–Wigderson reduction, this would give protocols of cost O(r^α) [3, 9].
- Sparse low-rank matrices. Does every n × n real matrix of rank r with at most εn² non-zero entries contain an all-zero submatrix with both sides at least n·exp(−O(√(εr))), as Lovett conjectured [3]?
- Signed rectangle rank. Is every Boolean matrix of rank r a signed sum of O(r) all-1 rectangles [11]?
- AND-functions. Can the log n factor be removed from the bound of Knop and colleagues [7]?
- Rank-Ramsey graphs. How small can the complement rank of n-vertex graphs with clique number at most 41 be, below O(n^(1−1/10000)) [10]?
Work on this in Papex
If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.
Key references
- Lovász, L. & Saks, M. (1988). Lattices, Möbius functions and communication complexity. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), 81–90. 10.1109/SFCS.1988.21924 · Checked 16 Oct 2026
- Huang, H. & Sudakov, B. (2012). A counterexample to the Alon–Saks–Seymour conjecture and related problems. Combinatorica 32(2), 205–219. 10.1007/s00493-012-2746-4 · Checked 16 Oct 2026
- Lovett, S. (2014). Recent advances on the log-rank conjecture in communication complexity. Bulletin of the EATCS 112 (Computational Complexity Column). Source · Checked 16 Oct 2026
- Lovett, S. (2016). Communication is bounded by root of rank. Journal of the ACM 63(1), 1–9. 10.1145/2724704 · Checked 16 Oct 2026
- Göös, M., Pitassi, T. & Watson, T. (2018). Deterministic communication vs. partition number. SIAM Journal on Computing 47(6), 2435–2450; conference version in FOCS 2015. 10.1137/16M1059369 · Checked 16 Oct 2026
- Chattopadhyay, A., Mande, N. S. & Sherif, S. (2020). The log-approximate-rank conjecture is false. Journal of the ACM 67(4), 1–28; conference version in STOC 2019. 10.1145/3396695 · Checked 16 Oct 2026
- Knop, A., Lovett, S., McGuire, S. & Yuan, W. (2021). Log-rank and lifting for AND-functions. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), 197–208. 10.1145/3406325.3450999 · Checked 16 Oct 2026
- Balodis, K., Ben-David, S., Göös, M., Jain, S. & Kothari, R. (2023). Unambiguous DNFs and Alon–Saks–Seymour. SIAM Journal on Computing, FOCS21-157–FOCS21-173; conference version in FOCS 2021. 10.1137/22M1480616 · Checked 16 Oct 2026
- Sudakov, B. & Tomon, I. (2025). Matrix discrepancy and the log-rank conjecture. Mathematical Programming 212(1–2), 567–579; published online 2024. 10.1007/s10107-024-02117-9 · Checked 16 Oct 2026
- Beniamini, G., Linial, N. & Shraibman, A. (2026). The Rank-Ramsey problem and the log-rank conjecture. Combinatorics, Probability and Computing 35(4), 568–597. 10.1017/S0963548326100455 · Checked 16 Oct 2026
- Hambardzumyan, L., Lovett, S. & Shirley, M. (2026). The log-rank conjecture: new equivalent formulations. In Computational Complexity Conference (CCC 2026), LIPIcs 383, 7:1–7:9. 10.4230/LIPIcs.CCC.2026.7 · Checked 16 Oct 2026
- Song, Z. (2026). Alphabet-preserving lifting for the log-rank conjecture. Preprint, arXiv:2608.01812 (version 1, 3 August 2026), not peer reviewed. Source · Checked 16 Oct 2026
- Wikipedia. List of unsolved problems in computer science (revision of 15 September 2026). Source · Checked 16 Oct 2026
Source
Open, as listed by Wikipedia · Unsolved problems in computer science. Checked 08 Oct 2026.
The status is the source’s. Papex does not decide whether a problem is solved.
Records on this problem
No public record addresses this problem yet.