Block structure in boolean matrices of bounded factorization norm

2025/07/01 by Marcel K. Goh, Hamed Hatami, Goh, Marcel K. +1
Computer Science · Engineering · #15B36 #47L80 #94D10 #Classical Analysis and ODEs (math.CA) #FOS: Mathematics #Matrix Theory and Algorithms #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2507.00872

openalex publication_date 2025/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 γ₂ factorization norm at most 1. Building on recent work by Balla, Hambardzumyan, and Tomon, we show that for any boolean matrix with γ₂ 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.

Citations

• Factorization norms and an inverse theorem for MaxCut
• C₄-free subgraphs of high degree with geometric applications
• Block complexity and idempotent Schur multipliers
• Structure in Communication Complexity and Constant-Cost Complexity Classes
• The discrepancy of greater-than
• On the Structure of Boolean Functions with Small Spectral Norm
• On the Ranges of Bimodule Projections
• On a Conjecture of Littlewood and Idempotent Measures

Cited by

• Factorization norms and an inverse theorem for MaxCut
• Block complexity and idempotent Schur multipliers

Related

• Factorization norms and an inverse theorem for MaxCut
• Boolean Rank via Monomial Ideals
• Factorization norms and Zarankiewicz problems
• Factorization of Binary Matrices: Rank Relations, Uniqueness and Model Selection of Boolean Decomposition
• On Minimally Non-Firm Binary Matrices