The monochromatic-rectangle formulation of the log-rank conjecture
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.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Lianna Hambardzumyan, Shachar Lovett and Morgan Shirley, “The Log-Rank Conjecture: New Equivalent Formulations”, arXiv:2510.02583 (2026).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.