Deterministic Graph Coloring in the Streaming Model

Speaker: Sepehr Assadi , Rutgers University

Date: Wednesday, March 02, 2022

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: https://mit.zoom.us/j/94625002202?pwd=bkROYjdBZStKeUIzVlNNTU11MVp6dz09

Event Type: Seminar

Room Description:

Host: Noah Golowich, MIT

Contact: Noah Golowich, nzg@csail.mit.edu

Relevant URL: https://mit.zoom.us/j/94625002202?pwd=bkROYjdBZStKeUIzVlNNTU11MVp6dz09

Speaker URL: https://people.cs.rutgers.edu/~sa1497/

Speaker Photo:
None

Reminders to: theory-seminars@csail.mit.edu, seminars@csail.mit.edu

Reminder Subject: 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).

Research Areas:
Algorithms & Theory

Impact Areas:

See other events that are part of the Algorithms and Complexity Seminar 2022.

Created by Noah Golowich at Monday, February 28, 2022 at 4:26 AM.