Deterministic Graph Coloring in the Streaming Model
, Rutgers University
Date: Wednesday, March 02, 2022
Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone
Event Type: Seminar
Host: Noah Golowich, MIT
Contact: Noah Golowich, firstname.lastname@example.org
Speaker URL: https://people.cs.rutgers.edu/~sa1497/
TALK: Deterministic Graph Coloring in the Streaming Model, Sepehr Assadi
Abstract: Recent breakthroughs in graph streaming have led to the design of single-pass semi-streaming algorithms for various graph coloring problems such as (Δ+1)-coloring, degeneracy-coloring, coloring triangle-free graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work.
In this talk, we will discuss our recent result that fully resolves this question: there is no deterministic single-pass semi-streaming algorithm that given a graph G with maximum degree Δ, can output a proper coloring of G using any number of colors which is sub-exponential in Δ. The proof is based on analyzing the multi-party communication complexity of a related communication game using elementary random graph theory arguments.
Based on joint work with Andrew Chen (Cornell) and Glenn Sun (UCLA).
Algorithms & Theory
Created by Noah Golowich at Monday, February 28, 2022 at 4:26 AM.