Yufei Zhao
Graph regularity method and applications to property testing
This tutorial gives an introduction to Szemerédi's graph regularity
lemma, a powerful tool in graph theory that gives a rough structural
description for all graphs, as well as its applications to computer
science, in particular to property testing. There are simple sampling
algorithms for inferring graph properties or estimating graph
parameters from reading a random selection of vertices in a graph,
though it is not always obvious how to prove guarantees about these
algorithms. The graph regularity lemma provides tools for analyzing
these algorithms.