Factorization norms and an inverse theorem for MaxCut

Igor Balla, Lianna Hambardzumyan, István Tomon

We prove that Boolean matrices with bounded ${\gamma }_2$-norm or bounded normalized trace norm must contain a linear-sized all-ones or all-zeros submatrix, verifying a conjecture of Hamba…