Tata Institute of Fundamental Research
(Δ + 1) Vertex Coloring in O(n) communication
STCS Student Seminar
Speaker:
Parth Mittal (University of Waterloo)
Organiser:
Hari Krishnan P A
Date:
Friday, 5 Jul 2024, 14:30 to 15:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
I will talk about the communication complexity of (Δ+1) vertex coloring, where the edges of an n-vertex graph of maximum degree Δ are partitioned between two players. I will show a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combined with a folklore Ω(n) lower bound, this settles the randomized communication complexity of (Δ+1)-coloring up to constant factors.
Based on joint work with Maxime Flin.
| Speaker: | Parth Mittal (University of Waterloo) |
| Organiser: | Hari Krishnan P A |
| Date: | Friday, 5 Jul 2024, 14:30 to 15:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
I will talk about the communication complexity of (Δ+1) vertex coloring, where the edges of an n-vertex graph of maximum degree Δ are partitioned between two players. I will show a randomized protocol which uses O(n) bits of communication and ends with both players knowing the coloring. Combined with a folklore Ω(n) lower bound, this settles the randomized communication complexity of (Δ+1)-coloring up to constant factors.
Based on joint work with Maxime Flin.