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.
References
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
No solutions have been posted yet.