BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Discrete Mathematics Group - ECPv6.18.4.1//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
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:20261201T163000
DTEND;TZID=Asia/Seoul:20261201T173000
DTSTAMP:20261109T145436Z
CREATED:20261106T160706Z
LAST-MODIFIED:20261109T145436Z
UID:13963-1796142600-1796146200@dimag.ibs.re.kr
SUMMARY:Saeed Odak\, Approximation Schemes for Hyperbolic TSP and Steiner Tree
DESCRIPTION:We give an approximation scheme for the TSP in $d$-dimensional hyperbolic space that has nearly optimal dependence on $\varepsilon$ under SH. For any fixed dimension $d\geq 2$ and for any $\varepsilon>0$ our randomized algorithm gives a $(1+\varepsilon)$-approximation in time $2^{O(1/\varepsilon^{d-1})}n^{1+o(1)}$. We also provide an algorithm for the hyperbolic Steiner tree problem with the same running time. \n\n\n\nOur algorithm is an Arora-style dynamic program based on a randomly shifted hierarchical decomposition. However\, we introduce a new hierarchical decomposition called the hybrid hyperbolic quadtree to achieve the desired large-scale structure\, which deviates significantly from the recently proposed hyperbolic quadtree of Kisfaludi-Bak and Van Wordragen (JoCG’25). Moreover\, we have a new non-uniform portal placement\, and our structure theorem employs a new weighted crossing analysis. We believe that these techniques could form the basis for further developments in geometric optimization in curved spaces. \n\n\n\nThis is a joint work with Sándor Kisfaludi-Bak\, Satyam Singh\, and Geert van Wordragen.
URL:https://dimag.ibs.re.kr/event/2026-12-01/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Asia/Seoul:20261208T163000
DTEND;TZID=Asia/Seoul:20261208T173000
DTSTAMP:20261106T160014Z
CREATED:20261012T113621Z
LAST-MODIFIED:20261106T160014Z
UID:13611-1796747400-1796751000@dimag.ibs.re.kr
SUMMARY:William J. Wesley\, An elementary solution to the 2-color Pythagorean triples problem
DESCRIPTION:In the 1980s\, Ron Graham asked whether every red/blue coloring of the positive integers contains a monochromatic Pythagorean triple and offered a $100 prize for the answer. The bounty was claimed in 2016 by Heule\, Kullmann\, and Marek\, who showed that every such coloring of [1\,7825] has a monochromatic triple. Their proof used SAT solvers and took over 50\,000 CPU hours to produce and verify. In this talk we will present an elementary solution to Graham’s problem that requires neither deep analytic arguments nor extensive computation.
URL:https://dimag.ibs.re.kr/event/2026-12-08/
LOCATION:Room B332\, IBS (기초과학연구원)
CATEGORIES:Discrete Math Seminar
END:VEVENT
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