- Sublinear Algorithms for (D...
- Edit Event
- Cancel Event
- Preview Reminder
- Send Reminder
- Other events happening in May 2019

## 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, joanne@csail.mit.edu

**Relevant URL:**

**Speaker URL:**
None

**Speaker Photo:**

None

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

**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:**

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