A Unified View of Graph Regularity via Matrix Decompositions

Greg Bodwin, Santosh Vempala

We prove algorithmic weak and \Szemeredi{} regularity lemmas for several classes of sparse graphs in the literature, for which only weak regularity lemmas were previously known. Th…