- Lower Bounds for Deterministic Graph Coloring in the Streaming Model
- Project Year:
2021
- REU Student (s):
Glenn Sun | University of California-Los Angeles CA
- Student 1 Institution:
University of California-Los Angeles
- Project Mentor:
Sepehr Assadi
- Project Mentor Area:
Computer Science
- Project Abstract:
In the graph semi-streaming model of computation, the input graph arrives as a stream and the goal is to compute solutions in O(n polylog n) space. With randomization, Assadi, Chen, and Khanna recently showed that the coloring problem for graphs of maximum degree Δ admits a solution in this model using an optimal Δ + 1 colors. However, little is known about this problem in deterministic settings. In this project, we showed that when Δ = Ω(n^{2/3}), no deterministic streaming algorithm can output proper colorings using O(n^{1-ε}) colors, for all ε > 0. In particular, any general algorithm for deterministic graph coloring must use at least Ω(Δ^{3/2 - ε}) colors.
