The paper “Expanders via Local Edge Flips in Quasilinear Time”, by George Giakkoupis, has been accepted at the 54th ACM Symposium on Theory of Computing (STOC 2022). Congratulations to George!
The paper provides a new analysis for a natural, local edge-flipping process, which shows that starting from any connected regular graph (of large enough degree), an expander graph is obtained almost surely after a quasilinear number of steps in the order of the graph.
This result provides a theoretical justification for the widespread use of edge-flip operations in practice.
