Large zero rectangle conjecture for low-rank sparse matrices
Large zero rectangle conjecture for low-rank sparse matrices
From papers
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.
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
Sign in to submit a solution.
No solutions have been posted yet.