학과 세미나 및 콜로퀴엄
Room B332, IBS (기초과학연구원)
이산수학
Saeed Odak (Department of Computer Science, Aalto University)
Approximation Schemes for Hyperbolic TSP and Steiner Tree
Room B332, IBS (기초과학연구원)
이산수학
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.
Our 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.
This is a joint work with Sándor Kisfaludi-Bak, Satyam Singh, and Geert van Wordragen.
In this talk, I will review my academic journey over the past 31 years. In particular, I will examine the domain decomposition method, which has played a central role in my work, as well as its applications in image processing and recent artificial neural networks. I will also discuss what constitutes good research, the aspects I find regrettable, and my future plans.
Room B332, IBS (기초과학연구원)
이산수학
William J. Wesley (IBS 이산수학그룹)
An elementary solution to the 2-color Pythagorean triples problem
Room B332, IBS (기초과학연구원)
이산수학
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.
The classical Simpson correspondence describes complex linear representations of the fundamental group of a smooth complex projective variety in terms of linear algebraic objects, namely Higgs bundles. Inspired by this, Gerd Faltings initiated in 2005 a p-adic analogue, with the aim of understanding continuous p-adic representations of the geometric fundamental group of a smooth projective variety over a p-adic local field.
The goal is to present recent joint work with M. Gros and T. Tsuji on the functoriality of the p-adic Simpson correspondence. We introduce a new method for twisting Higgs modules via Higgs-Tate algebras. This construction builds on our earlier joint work with M. Gros on the p-adic Simpson correspondence, which it recovers as a special case. The resulting framework provides twisted pullbacks and higher direct images of Higgs modules, making it possible to study the functoriality of the p-adic Simpson correspondence under arbitrary pullbacks and proper (log-)smooth direct images, including for morphisms that do not lift to the infinitesimal deformations used in the construction of the correspondence.
In the colloquium lecture, we will give a brief introduction to the correspondence, starting from its p-adic origin, namely Sen theory. I will present the general ideas, while discussing the constructions and results only in the local setting.
The more technical second lecture on Friday will present our global approach to the p-adic Simpson correspondence, twisted pullbacks, and higher direct images of Higgs modules, together with the corresponding functoriality results. I will also illustrate our approach with a new construction of the Sen endomorphism.
The classical Simpson correspondence describes complex linear representations of the fundamental group of a smooth complex projective variety in terms of linear algebraic objects, namely Higgs bundles. Inspired by this, Gerd Faltings initiated in 2005 a p-adic analogue, with the aim of understanding continuous p-adic representations of the geometric fundamental group of a smooth projective variety over a p-adic local field.
The goal of the two lectures is to present recent joint work with M. Gros and T. Tsuji on the functoriality of the p-adic Simpson correspondence. We introduce a new method for twisting Higgs modules via Higgs-Tate algebras. This construction builds on our earlier joint work with M. Gros on the p-adic Simpson correspondence, which it recovers as a special case.
The resulting framework provides twisted pullbacks and higher direct images of Higgs modules, making it possible to study the functoriality of the p-adic Simpson correspondence under arbitrary pullbacks and proper (log-)smooth direct images, including for morphisms that do not lift to the infinitesimal deformations used in the construction of the correspondence.
Continuing the colloquium lecture on Thursday, which was an introduction to the subject, in this second, more technical lecture, will present our global approach to the p-adic Simpson correspondence, twisted pullbacks, and higher direct images of Higgs modules, together with the corresponding functoriality results.
I will also illustrate our approach with a new construction of the Sen endomorphism.
Room B332, IBS (기초과학연구원)
이산수학
Jaehyun Koo (Massachusetts Institute of Technology)
Dynamic Graph Coloring: Sequential, Parallel, and Distributed
Room B332, IBS (기초과학연구원)
이산수학
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.
In 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.
A 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.
The talk is based on the joint work with Mohsen Ghaffari (MIT).
