Sublinear Algorithms for (Delta+1) Vertex Coloring

Speaker: Sepehr Assadi , Princeton University

Date: Tuesday, May 21, 2019

Time: 4:00 PM to 5:00 PM

Public: Yes

Location: 32-G449

Event Type:

Room Description:

Host: Prof. Ronitt Rubinfeld

Contact: Joanne Talbot Hanley, 617-253-6054,

Relevant URL:

Speaker URL: None

Speaker Photo:

Reminders to:,

Reminder Subject: TALK: TOC Seminar: Sepehr Assadi "Sublinear Algorithms for (Delta+1) Vertex Coloring", Tuesday, May 21 at 4pm!

Abstract: In this talk, we will examine a classical graph coloring problem through the lens of sublinear algorithms—these are algorithms that use computational resources that are substantially smaller than the size of the input on which they operate. It is well-known that any graph with maximum degree Delta admits a proper vertex coloring with (Delta + 1) colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We will present results that answer this question in the affirmative for several well-studied models of sublinear computation, most notably graph streaming and sublinear time algorithms. We obtain these results by proving a palette sparsification theorem which says that if every vertex independently samples O(log n) colors from the available Delta+1 colors, then almost certainly a (Delta + 1) coloring can be found using only the sampled colors. We then show that this palette sparsification theorem naturally leads to essentially optimal sublinear algorithms in each of the above-mentioned models of computation.

Based on joint work with Yu Chen and Sanjeev Khanna.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation Seminar (ToC) 2019.

Created by Joanne Talbot Hanley Email at Wednesday, May 15, 2019 at 11:26 AM.