The monochromatic-rectangle formulation of the log-rank conjecture
Let be a Boolean matrix, and let a monochromatic rectangle be a submatrix all of whose entries have the same value. Let denote the rank of over the reals, and define the density of a rectangle as its number of entries divided by the total number of entries of . Monochromatic-rectangle formulation. Any Boolean matrix has a monochromatic rectangle of density
The source identifies this as an equivalent version of the log-rank conjecture due to Nisan and Wigderson. Since the log-rank conjecture is stated to remain unsolved, this formulation is also open.
References
Primary source
Lianna Hambardzumyan, Shachar Lovett and Morgan Shirley, “The Log-Rank Conjecture: New Equivalent Formulations”, arXiv:2510.02583 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.