Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
Summary: Deterministic semi-streaming algorithm achieves combinatorially optimal (Δ+1)-coloring in O(log Δ · log log Δ) passes, improving prior O(Δ)-coloring. Adversarially-robust semi-streaming reduced colors to O(Δ^{5/2}) with improved colors/space tradeoffs (e.g., O(Δ^2) colors in O(n·Δ^{1/3}) space). (summarized by gpt-5-mini on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Sepehr Assadi
- 2. Amit Chakrabarti
- 3. Prantar Ghosh
- 4. Manuel Stoeckl
Incoming Citations (Sorted by Pagerank)
Showing 1 of 1 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 10,353 | Perfect Sampling in Turnstile Streams Beyond Small Moments | 2025 | PODS | 4.1945683e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 3 of 3 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 4,172 | The Adversarial Robustness of Sampling | 2020 | PODS | 6.3879072e-05 |
| 4,403 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2194225e-05 |
| 5,392 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5329138e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,749 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS | 8.1773535e-05 |
| 11,833 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD | 4.1945683e-05 |
| 5,046 | Better Algorithms for Counting Triangles in Data Streams | 2016 | PODS | 5.7405307e-05 |
| 8,533 | How the Degeneracy Helps for Triangle Counting in Graph Streams | 2020 | PODS | 4.4937074e-05 |
| 9,877 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB | 4.2656547e-05 |
| 11,332 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 4.1945683e-05 |
| 11,306 | Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality | 2023 | VLDB | 4.1945683e-05 |
| 4,403 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2194225e-05 |
| 5,751 | Effective and Efficient Dynamic Graph Coloring | 2018 | VLDB | 5.3409543e-05 |
| 11,321 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1945683e-05 |