The factorization norm and an inverse theorem for MaxCut

In this talk, we will present a proof of the fact 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 Hambardzumyan, Hatami, and Hatami. We will also discuss further structural results about Boolean matrices of bounded \(\gamma_2\)-norm and applications in communication complexity, operator theory, spectral graph theory, and extremal combinatorics.

As a key application, we establish a theorem for MaxCut which contrasts a celebrated result of Edwards. In particular, we show that if the MaxCut of \(G\) is at most \(m/2 + O(\sqrt m)\), then \(G\) must contain a clique of size \(\Omega(\sqrt m)\).

This talk regards joint work with Lianna Hambardzumyan and István Tomon.