Sublinear Insights: A Faster (Classical) Algorithm for Edge Coloring

on YouTube ↗34m

" summary

Presents a randomized algorithm that outputs a Delta+O(log n) coloring in O(m log Delta) expected time, using ideas from McGregor (streaming) and Goel‑Kapralov‑Khanna (random‑walk rounding). It samples fair matchings via randomized walks so each max‑degree vertex is matched with ~1/Delta probability, colors most edges, and leaves a leftover set of max degree O(log n). Combining this with Vizing’s procedure yields an O(n^2 log n) expected Delta+1 algorithm; a concurrent work achieves ~O(m n^{1/3}).

AI-written summary · about

" chapters (15)

1. 0:00Edge coloring problem
2. 1:02Problem definition and background
3. 3:13Known results and Vizing's theorem
4. 4:20Algorithmic runtime history
5. 6:28Delta plus log n coloring in near-linear time
6. 8:35Corollaries and implications
7. 12:05Comparison with concurrent work
8. 14:39New algorithm overview
9. 15:24Regular bipartite graphs sublinear time
10. 17:59GKK approach for bipartite delta coloring
11. 19:43Extending to general graphs challenges
12. 21:07Fair matching sampling
13. 25:00General graph edge coloring steps
14. 27:53Correctness and runtime analysis
15. 29:19Conclusion and open problems