The monochromatic-rectangle formulation of the log-rank conjecture

From papers

Let MM be a Boolean matrix, and let a monochromatic rectangle be a submatrix all of whose entries have the same value. Let r(M){\mathrm{r}}(M) denote the rank of MM over the reals, and define the density of a rectangle as its number of entries divided by the total number of entries of MM. Monochromatic-rectangle formulation. Any Boolean matrix MM has a monochromatic rectangle of density

2polylog(r(M)).2^{-\operatorname{polylog}({\mathrm{r}}(M))}.

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

No solutions have been posted yet.