Quick Approximation to Matrices and Applications III: The Atoms of a Cut Decomposition with Error εn² Form a 2ε-Pseudo-Regular Partition of a GraphResearch Paper
Szemerédi's regularity lemma partitions the vertex set of any graph into a bounded number of parts between which edges are distributed almost randomly. It is a central tool of extremal graph theory, but the number of parts it needs is a tower of exponentials in , which makes it unusable in algorithms. In 1996 and 1999 Frieze and Kannan introduced…