A Fast New Algorithm for Weak Graph Regularity

Regularity lemmas are very useful tools in graph theory and theoretical computer science. In this talk, I'll discuss a recent deterministic algorithm that finds, in $\epsilon^{-O(1)} n^2$ time, an $\epsilon$-regular Frieze--Kannan partition of a graph on $n$ vertices. The algorithm outputs an approximation of a given graph as a weighted sum of $\epsilon^{-O(1)}$ many complete bipartite graphs. Joint work with Jacob Fox and Yufei Zhao.