Large zero rectangle conjecture for low-rank sparse matrices

About 13 years old · traced to

Let MM be an n×nn \times n real matrix with rank⁡(M)=r\operatorname{rank}(M)=r and such that Mi,j≠0M_{i,j} \ne 0 for at most εn2\varepsilon n^2 entries. A large zero rectangle conjecture asserts that there exist A,B⊂[n]A,B \subset [n] such that

Ma,b=0∀a∈A,b∈BM_{a,b}=0 \qquad \forall a \in A, b \in B

and

∣A∣,∣B∣≥n⋅exp⁡(−O(εr)).|A|,|B| \ge n \cdot \exp(-O(\sqrt{\varepsilon r})).

This conjecture seeks to generalize the large monochromatic-rectangle phenomenon used in deterministic communication complexity from Boolean matrices to low-rank sparse real matrices. The supplied text gives no evidence that the conjecture has been resolved.

References

Primary source

Shachar Lovett, “Communication is bounded by root of rank”, arXiv:1306.1877 (2013).

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.