Block structure in boolean matrices of bounded factorization norm

Abstract

A boolean matrix is blocky if its $1$-entries form a collection of 1-monochromatic submatrices that are disjoint in both rows and columns. Blocky matrices are precisely the set of boolean matrices with ${\hat{I}}_2^3$ factorization norm at most $1$. Building on recent work by Balla, Hambardzumyan, and Tomon, we show that for any boolean matrix with ${\hat{I}}_2^3$ norm at most $\hat{I}»$, there exists a a collection of row- and column-disjoint 1-monochromatic submatrices that together cover a significant portion (at least a $1/2^{2^{O(\hat{I}»)}}$ fraction) of its $1$-entries.

14 pages