Large zero rectangle conjecture for low-rank sparse matrices

From papers

Let MM be an n×nn \times n real matrix with rank(M)=r\operatorname{rank}(M)=r and such that Mi,j0M_{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=0aA,bBM_{a,b}=0 \qquad \forall a \in A, b \in B

and

A,Bnexp(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.

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

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

Solutions 0

No solutions have been posted yet.