Bounded cgamma2cgamma_2-norm decomposition conjecture for Boolean matrices

Let MM be an m×nm\times n Boolean matrix, and let γ2(M)\gamma_2(M) denote its γ2\gamma_2-norm. A blocky matrix is a blow-up of a permutation matrix. Bounded γ2\gamma_2-norm decomposition conjecture. If

γ2(M)γ,\gamma_2(M)\leq \gamma,

then there exists a constant cγc_{\gamma} depending only on γ\gamma such that MM is a ±1\pm1-linear combination of at most cγc_{\gamma} blocky matrices.

The conjecture is equivalent, according to the source, to a structural characterization of matrices with bounded γ2\gamma_2-norm and to an open question about characterizing idempotent Schur multipliers in terms of contractive idempotents.

Sources & referencesView supporting material

Primary source

Igor Balla, Lianna Hambardzumyan and István Tomon, “Factorization norms and an inverse theorem for MaxCut”, arXiv:2506.23989 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.