Block structure in boolean matrices of bounded factorization norm
Block structure in boolean matrices of bounded factorization norm
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 $γ_2$ factorization norm at most $1$. Building on recent work by Balla, Hambardzumyan, and Tomon, we show that for any boolean matrix with $γ_2$ norm at most $λ$, 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(λ)}}$ fraction) of its $1$-entries.
Marcel K. Goh、Hamed Hatami
数学
Marcel K. Goh,Hamed Hatami.Block structure in boolean matrices of bounded factorization norm[EB/OL].(2025-07-15)[2025-07-17].https://arxiv.org/abs/2507.00872.点此复制
评论