Lovett's sparse low-rank matrix conjecture

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

nexp(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.

Sources & referencesView supporting material

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.