Graph Coloring Through the Sublinear Lens
summary
Shows that sampling O(log n) colors per vertex from the Δ+1 palette suffices so the graph is list-colorable from those lists (called palette sparsification), and that remaining “relevant” edges drop to about n log^2 n. That yields an algorithmic version that finds a Δ+1 coloring by adaptive greedy sampling in Õ(n^{3/2}) time, extends to one-round MPC/streaming formats, and has matching ln n and n^{3/2} barriers.
AI-written summary · about
chapters (12)
- 0:00Sublinear algorithms and graph coloring
- 1:06Why sublinear algorithms are hard
- 4:21Vertex coloring and delta+1
- 8:05Delta+1 coloring in sublinear time?
- 15:21Randomized delta+1 coloring algorithm
- 23:01Palette sparsification for coloring
- 31:25Palette sparsification in MPC and streaming
- 34:46Simpler linear-time delta+1 coloring
- 40:03Õ(n^(3/2)) vertex coloring
- 54:55Edge coloring in sublinear models
- 59:01Sublinear ideas in edge coloring
- 1:01:12Summary and future directions
related talks
16mSpatial Programming for Environmental Monitoring
32mInteraction of color systems
45mYou need to know Algorithms and Data Structures in Front-end anyway
49mThe 1 Trillion Pixel Maze: My Decade-Long Obsession with C# Optimization
49mMagenta is a Lie - and Other Tales of Abstraction
55mBack to Basics: Algorithmic Complexity
12mWhoa, pictures! A visual history of visual programming languages!
46mArchitectural Decisions for Interactive Viz