Adversarially Robust Coloring for Graph Streams

on YouTube ↗37m

" summary

Shows a concrete lower bound: any adversarially robust k‑coloring algorithm for Δ‑bounded graphs uses Ω(n Δ^2 / k) space, so robust Δ+1 or O(Δ) colorings force linear space and any robust semi‑streaming algorithm needs Ω(Δ^2) colors. Gives matching positive results: a Δ^2 coloring in n·√Δ space for insert‑only streams and a Δ^3 algorithm in semi‑streaming space via a palette/specification scheme, plus a generalization trading colors for space.

AI-written summary · about

" chapters (20)

1. 0:00Intro
2. 0:13The Data Streaming Model
3. 1:40Oblivious Adversary: Standard Streaming
4. 2:42Adaptive Adversary: Robust Streaming
5. 4:53Problem: Streaming Graph Coloring
6. 7:08Our Results: Lower Bounds
7. 10:28Prior Work: Adversarial Robustness
8. 11:58Prior Work: Separation Results
9. 13:58In Search of A Natural Separation
10. 15:47Natural Separation: Insertion-Only
11. 17:29Separation for Graph Coloring
12. 18:07The Subset-Avoidance Problem
13. 18:55Reduction from AVOID to Robust Coloring
14. 24:15Robust Coloring Algorithms
15. 24:31The Sketch-Switching Framework
16. 27:17A Sketch-Switching Based Coloring Algorit
17. 30:16The Palette-Sparsification Framework
18. 31:50A Palette Sparsification Based Algorithm
19. 35:32Conclusions
20. 36:00Open Problems