Lovett's sparse low-rank matrix conjecture

At least 1 year old · documented by

Let MM be an n×nn\times n real matrix of rank rr, and suppose that at most εn2\varepsilon n^2 entries of MM are nonzero, where ε∈(0,1/2)\varepsilon\in(0,1/2).

Lovett's conjecture. The matrix MM contains an all-zero square submatrix of size at least

n⋅exp⁡(−O(εr)).n\cdot\exp(-O(\sqrt{\varepsilon r})).

The conjecture concerns large zero rectangles in sparse low-rank matrices and is motivated by the log-rank problem. The supplied text does not state whether it has been resolved.

References

Primary source

Zach Hunter, Aleksa Milojević, Benny Sudakov and István Tomon, “Disjoint pairs in set systems and combinatorics of low rank matrices”, arXiv:2411.13510 (2024).

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.