A Simple Algorithm for Constructing Szemerédi's Regularity Partition

Alan Frieze, Ravi Kannan

Abstract


We give a simple constructive version of Szemerédi's Regularity Lemma, based on the computation of singular values of matrices.


Full Text: PDF