BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20220313T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20211107T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20221004T092808Z
UID:f72d5b78-5be3-400d-bada-e0aff36ad13e
DTSTART;TZID=America/New_York:20220302T160000
DTEND;TZID=America/New_York:20220302T170000
CREATED:20220228T042601
DESCRIPTION:Abstract: Recent breakthroughs in graph streaming have led to t
he design of single-pass semi-streaming algorithms for various graph color
ing problems such as (Δ+1)-coloring\, degeneracy-coloring\, coloring tria
ngle-free graphs\, and others. These algorithms are all randomized in cruc
ial ways and whether or not there is any deterministic analogue of them ha
s remained an important open question in this line of work.\n\nIn this tal
k\, we will discuss our recent result that fully resolves this question: t
here 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 communica
tion game using elementary random graph theory arguments. \n\nBased on joi
nt work with Andrew Chen (Cornell) and Glenn Sun (UCLA).
LAST-MODIFIED:20220228T042601
LOCATION:https://mit.zoom.us/j/94625002202?pwd=bkROYjdBZStKeUIzVlNNTU11MVp6
dz09
SUMMARY:Deterministic Graph Coloring in the Streaming Model
URL:https://calendar.csail.mit.edu/events/244784
END:VEVENT
END:VCALENDAR