BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.18.2//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Discrete Mathematics Group
X-ORIGINAL-URL:https://dimag.ibs.re.kr
X-WR-CALDESC:Events for Discrete Mathematics Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:Asia/Seoul
BEGIN:STANDARD
TZOFFSETFROM:+0900
TZOFFSETTO:+0900
TZNAME:KST
DTSTART:20250101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261215T163000
DTEND;TZID=Asia/Seoul:20261215T173000
DTSTAMP:20261024T235903Z
CREATED:20261024T235903Z
LAST-MODIFIED:20261024T235903Z
UID:13908-1797352200-1797355800@dimag.ibs.re.kr
SUMMARY:Jaehyun Koo (구재현)\, Dynamic Graph Coloring: Sequential\, Parallel\, and Distributed
DESCRIPTION:For any graph with maximum degree at most $\Delta$\, a simple inductive argument shows that the graph can be properly colored using $\Delta+1$ colors. However\, a direct implementation of this argument is highly sequential\, motivating extensive research into efficient algorithms in parallel\, distributed\, and dynamic settings. \nIn this talk\, I will present a simple randomized algorithm that efficiently maintains a $(\Delta+1)$-coloring under edge insertions and deletions. Despite its remarkably simple implementation\, the algorithm requires a subtle analysis due to its heavy use of randomization. I will also discuss prior and related work on the development of highly efficient $(\Delta+1)$-coloring algorithms. \nA key advantage of this algorithm is its ability to process many updates simultaneously\, which makes it naturally adaptable to parallel and distributed computations. In the sequential setting\, the algorithm processes each update in $O(1)$ expected time\, worst-case. More importantly\, the algorithm admits a natural implementation in both parallel setting and the distributed CONGEST setting\, with $O(1)$ expected work and message per update in a batch in $poly(\log n)$ depth and round with high probability. This is\, in a sense\, an ideal parallelization of the above results. \nThe talk is based on the joint work with Mohsen Ghaffari (MIT).
URL:https://dimag.ibs.re.kr/event/2026-12-15/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
END:VCALENDAR