The monochromatic-rectangle formulation of the log-rank conjecture

About 1 year old · traced to

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

2−polylog⁡(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.

References

Primary source

Lianna Hambardzumyan, Shachar Lovett and Morgan Shirley, “The Log-Rank Conjecture: New Equivalent Formulations”, arXiv:2510.02583 (2026).

Progress summary

Never refreshed

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.