Bounded -norm decomposition conjecture for Boolean matrices
Bounded -norm decomposition conjecture for Boolean matrices
Let be an Boolean matrix, and let denote its -norm. A blocky matrix is a blow-up of a permutation matrix. Bounded -norm decomposition conjecture. If
then there exists a constant depending only on such that is a -linear combination of at most blocky matrices.
The conjecture is equivalent, according to the source, to a structural characterization of matrices with bounded -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.