Thursday, February 19, 2026

2026-02-24 / 16:30 ~ 17:30

IBS-KAIST 세미나 - 이산수학: Strongly Polynomial Parallel Work-Depth Tradeoffs for Directed SSSP

by Marek Sokołowski(Max Planck Institute of Informatics)

In this talk, we show new strongly polynomial work-depth tradeoffs for computing single-source shortest paths (SSSP) in non-negatively weighted directed graphs in parallel. Most importantly, we prove that directed SSSP can be solved within $\widetilde{O}(m+n^{2-\varepsilon})$ work and $\widetilde{O}(n^{1-\varepsilon})$ depth for some positive $\varepsilon>0$. For dense graphs with non-negative real weights, this yields the first nearly work-efficient strongly polynomial algorithm with sublinear depth. Moreover, we develop efficient parallel algorithms in the Word RAM model for several variants of SSSP in graphs with exponentially large edge weights. This is a joint work with Adam Karczmarz and Wojciech Nadara.

2026-02-26 / 13:30 ~ 15:30

학과 세미나/콜로퀴엄 - 기타: Birational Geometry of Fibered Surfaces #3

by 이동규, 안세준()

This is a reading seminar for two graduate students.) This talk studies the birational geometry of fibered surfaces, which are integral, projective, flat schemes of dimension 2 over a Dedekind scheme. In contrast to smooth projective curves, birational equivalence for surfaces does not imply isomorphism, which leads to the problem of understanding and selecting canonical representatives within a birational class. We first introduce basic tools for birational surface theory, including blowing-ups, contraction, and desingularization. We then explain how intersection theory on regular surfaces is used to analyze these operations and to identify exceptional curves. This perspective naturally leads to minimal surfaces and to applications of contraction criteria in the construction of canonical models.

Events for the 취소된 행사 포함