Large zero rectangle conjecture for low-rank sparse matrices
Let be an real matrix with and such that for at most entries. A large zero rectangle conjecture asserts that there exist such that
and
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.