Talks
Spring 2017
![](https://old.simons.berkeley.edu/sites/default/files/styles/workshop_main/public/pseudo_placeholder_final.png?itok=6hVd5UbS)
Algorithmic Regularity Lemmas and Applications
Wednesday, March 8th, 2017, 3:30 pm–4:00 pm
Speaker:
Location:
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.
Attachment | Size |
---|---|
![]() | 630.56 KB |