Spring 2017

Algorithmic Regularity Lemmas and Applications

Wednesday, March 8th, 2017 3:30 pm4:00 pm

Add to Calendar


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.