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,365 | Perfect Sampling in Turnstile Streams Beyond Small Moments | 2025 | PODS | 4.1905499e-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,170 | The Adversarial Robustness of Sampling | 2020 | PODS | 6.381766e-05 |
| 4,399 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2134435e-05 |
| 5,397 | Coloring Away Communication in Parallel Query Optimization | 1995 | VLDB | 5.5277465e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 2,755 | Towards Tight Bounds for the Streaming Set Cover Problem | 2016 | PODS | 8.1694565e-05 |
| 11,841 | Streaming Algorithms for Robust Distinct Elements | 2016 | SIGMOD | 4.1905499e-05 |
| 5,043 | Better Algorithms for Counting Triangles in Data Streams | 2016 | PODS | 5.7350154e-05 |
| 8,532 | How the Degeneracy Helps for Triangle Counting in Graph Streams | 2020 | PODS | 4.4893996e-05 |
| 9,876 | Color: A Framework for Applying Graph Coloring to Subgraph Cardinality Estimation | 2025 | VLDB | 4.2615675e-05 |
| 11,334 | The White-Box Adversarial Data Stream Model | 2022 | PODS | 4.1905499e-05 |
| 11,308 | Quasi-stable Coloring for Graph Compression: Approximating Max-Flow, Linear Programs, and Centrality | 2023 | VLDB | 4.1905499e-05 |
| 4,399 | A Framework for Adversarially Robust Streaming Algorithms | 2020 | PODS | 6.2134435e-05 |
| 5,764 | Effective and Efficient Dynamic Graph Coloring | 2018 | VLDB | 5.3358197e-05 |
| 11,323 | Approximately Counting Subgraphs in Data Streams | 2022 | PODS | 4.1905499e-05 |