Even the Easiest(?) Graph Coloring Problem is not Easy in Streaming!

on YouTube ↗36m

" summary

Establishes one-pass streaming bounds for estimating the number of monochromatic edges given a coloring: an algorithm that stores sample R of size n/√T (first n/√T vertices in random order), computes per-vertex projected monochromatic degrees to classify vertices as high or low, and uses Chernoff bounds plus bucketing to get space about Θ(n/√T) for conflict estimation when the promise is at least T monochromatic edges. A matching-style lower bound comes from a reduction from a multi‑party set problem on a hard instance that is partitioned into n/√T cliques, giving a provable Ω(n/T²) lower bound for one pass, leaving a gap between upper and lower in the random-order model.

AI-written summary · about

" chapters (11)

1. 0:00Graph coloring in streaming
2. 1:49Conflict estimation problem
3. 3:14Recent works on coloring
4. 5:23Vertex arrival models
5. 7:33Our results overview
6. 9:01Upper bound for random model
7. 14:04Algorithm design observations
8. 23:04Lower bound for random model
9. 25:37Communication complexity
10. 34:37Results and open questions
11. 36:05Q&A