In the same paper [11], Lovett proposed to study the size of all-zero rectangles in low-rank sparse real matrices, stating the following conjecture.
Statement
In the same paper [11], Lovett proposed to study the size of all-zero rectangles in low-rank sparse real matrices, stating the following conjecture. Conjecture 5 ([11]). Let M be an n \times n real matrix with rank(M ) = r such that at most \varepsilonn2 entries of M are not zero, where \varepsilon \in (0,\sqrt{ }1/2). Then M contains an all-zero square submatrix of size at least n \cdot exp(−O( \varepsilonr)). \sqrt{ } A construction achieving the bound n \cdot exp(−O( \varepsilonr)) can be constructed with the help of set systems. Given a pair of set systems A, B \subset 2[r] , the intersection matrix of (A, B) is the matrix M , whose rows and columns are indexed by the elements of A and B, respectively, and M (A, B) = |A\capB|. Note that rank(M ) \leq r. Construction. Let F = [r] \sqrt{ } k be the family of all k-element subsets of [r], where k = \varepsilonr, and let M2 be the n \times n intersection matrix of (F , F ), where n = kr . The report passage is retained verbatim as the relevant context for this extracted problem.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.