Event Series
Event Type
Seminar
Thursday, September 26, 2019 2:00 PM
László Miklós Lovász (MIT)

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 (whose joint refinement gives the partition), which in some cases can be of more use than just the partition.