Abstract: An n-vertex graph with maximum degree D is (D+1)-colorable: an almost trivial combinatorial result, with an equally simple greedy algorithm to produce a
(D+1)-coloring. However, given a stream of edges of such a graph, can we maintain a valid (D+1)-coloring as the edges arrive, while using not much more than O(n) space? What if the edges are chosen by an adversary who can look at our current coloring and add additional edges to try to confound us? This is the setting of **adversarially robust** streaming algorithms and this talk is about the coloring problem in this setting.
We obtain upper and lower bound results for this problem. In O(n polylog n) space, we can maintain an O(D^(5/2))-coloring of such an adversarial graph. On the other hand, every adversarially robust coloring algorithm under the same space limitation must spend Omega(D^2) colors. We in fact prove more general results that trade off the space usage against the color budget. As a by-product of our work, we obtain (i) a nuanced understanding of the power of randomness in streaming algorithms and (ii) more concretely, the first randomized-vs-deterministic separation for the (ordinary, non-robust) streaming graph coloring problem.
Based on joint works [C.-Ghosh-Stoeckl] and [Assadi-C.-Ghosh-Stoeckl].
Bio: Amit Chakrabarti is a Professor in the Department of Computer Science at Dartmouth College. He holds a Ph.D. in Computer Science from Princeton University and a B.Tech. in Computer Science from the Indian Institute of Technology, Bombay, where he was the President of India Gold Medalist.
Professor Chakrabarti's research is in the broad area of theoretical computer science. Specific interests are (1) complexity theory, especially communication complexity and applications of information theory, and (2) algorithms, including space-efficient algorithms for massive data streams. He is particularly known as a pioneer of the concept of "information complexity". His research has been funded by several awards from the National Science Foundation, including a CAREER award.