Calvin Lab Auditorium
Regularity lemmas are very useful tools in graph theory and theoretical computer science. They roughly involve dividing a graph into a bounded number of parts such that the graph looks in some sense like a graph that is pseudorandom between the pairs. Due to these applications, having algorithmic versions is of interest. We review a recent algorithmic version of the (weak) Frieze-Kannan regularity lemma, and give some applications to finding strong regular partitions, and subgraph counting. Joint work with Jacob Fox and Yufei Zhao.