Detailed schedule
- 17.02.2026: Optimal Algorithm for the Planar Two-Center Problem, Kyungjin Cho
Abstract
The planar two-center problem is a classical problem in computational geometry: given n points in the Euclidean plane, the goal is to compute two smallest congruent disks whose union covers all the points. Designing an optimal algorithm for this problem had remained a long-standing open question for several decades.
In SoCG 24, this open problem was resolved by presenting a deterministic O(nlogn)-time algorithm, which matches the known lower bound. In this seminar, I will present the key ideas underlying the optimal algorithm and provide a high-level sketch of its structure. In addition, I will introduce several historically significant results that shaped the development of the problem, highlighting their core algorithmic ideas (including the dynamic circular hull structures under monotone updates [SoCG 20]).
For details see the full paper. - 24.02.2026: TBA, Kritika Kashyap
- 02.03.2026: Slot not yet taken
- 09.03.2026: EuroCG talks part 1
- 16.03.2026: EuroCG talks part 2
Previous talks
-
10.02.2026: Combinatorial Reconfiguration: Flipping Non-Crossing Spanning Trees [Ferran Hurtado Memorial Lecture from the Canadian Conference on Computational Geometry 2025],
Birgit Vogtenhuber
Abstract
In this talk, I will report on flips in non-crossing spanning trees. For a set P of n points in the plane, a non-crossing (geometric) spanning tree is a spanning tree of the points in which every edge is a straight-line segment between a pair of points and no two edges intersect except at a common endpoint. In its most general form, an edge flip in a non-crossing spanning tree T of P is the operation of removing one edge from T and adding another edge such that the resulting structure is again a non-crossing spanning tree of P . Besides this edge flip, several more restricted flip operations have been considered for spanning trees. Most notably these include compatible edge flips (where the exchanged edges are non-crossing), rotations (where the exchanged edges share an endpoint), and edge slides (where the exchanged edges together with some third edge form an uncrossed triangle).
The problem of transforming one non-crossing spanning tree into another one via a sequence of flip operations of some type has been widely studied. Such a transformation is always possiblewith a finite number of flips even for the case of edge slides, which is the most restricted of the flip operations. I will review recent results concerning bounds on the number of flips that are sometimes required and always sufficient. I will close with some remarks on possible properties of shortest flip sequences, the algorithmic question of finding such sequences, and some open problems. - 03.02.2026: Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity,
Tijn de Vos, SlidesAbstract
A tree-packing is a collection of spanning trees of a graph. It has been a useful tool for computing the minimum cut in static, dynamic, and distributed settings. In particular, [Thorup, Comb. 2007] used them to obtain his dynamic min-cut algorithm with Õ(λ^{14.5}√n) worst-case update time. We reexamine this relationship, showing that we need to maintain fewer spanning trees for such a result; we show that we only need to pack Θ(λ^3 log m) greedy trees to guarantee a 1-respecting cut or a trivial cut in some contracted graph.
Based on this structural result, we then provide a deterministic algorithm for fully dynamic exact min-cut, that has Õ(λ^{5.5}√n) worst-case update time, for min-cut value bounded by λ. In particular, this also leads to an algorithm for general fully dynamic exact min-cut with Õ(m^{1-1/12}) amortized update time, improving upon Õ(m^{1-1/31}) [Goranci et al., SODA 2023].
We also give the first fully dynamic algorithm that maintains a (1+ε)-approximation of the fractional arboricity -- which is strictly harder than the integral arboricity. Our algorithm is deterministic and has O(α log^6(m/ε^4)) amortized update time, for arboricity at most α. We extend these results to a Monte Carlo algorithm with O(poly(log m,ε^{-1})) amortized update time against an adaptive adversary. Our algorithms work on multi-graphs as well.
Both result are obtained by exploring the connection between the min-cut/arboricity and (greedy) tree-packing. We investigate tree-packing in a broader sense; including a lower bound for greedy tree-packing, which -- to the best of our knowledge -- is the first progress on this topic since [Thorup, Comb. 2007]. - 27.01.2026: Small Empty Cycles in Simple Drawings of K_n, Anna Hofer, Slides
Abstract
Abstract: Given a simple drawing of a graph, a sub-drawing of a plane cycle of length k induces two connected regions of the plane. If one of the two regions does not contain any of the remaining vertices of the drawing, we call the cycle an empty plane k-cycle. In this talk, we consider simple drawings of the complete graph K_n and examine them with respect to the existence of empty plane k-cycles for small k. For k=3,4 it is known, that every vertex is incident to at least two empty plane k-cycles. We show that every vertex in a simple drawing of K_n is also incident to an empty plane k-cycle with k=5 or k=6.
This is joint work with Joachim Orthaber, Birgit Vogtenhuber, and Alexandra Weinberger. - 20.01.2026: The Algebraic Approach to Promise Constraint Satisfaction, Iris Hebbeker, Slides
Abstract
A constraint satisfaction problem (CSP) is a computational problem involving variables and constraints. The question is whether there is a variable assignment satisfying all constraints. Many well-known problems, such as k-SAT and k-colouring, can be defined in this framework. The hardness of CSPs is closely related to algebraic properties of their solution sets. More precisely, problems admitting certain types of polymorphisms are tractable, while those with only trivial polymorphisms are NP-hard.
In a promise constraint satisfaction problem (PCSP), one has to consider two sets of constraints; one stricter than the other. The goal is to decide between satisfiability of the strict constraints and unsatisfiability of the more relaxed ones. Using a suitable version of polymorphisms, even this extended version can be studied using algebraic methods. This theory was in part developed by [Barto, Bulín, Krokhin, Opršal 2019], who used it to show that it is NP-hard to distinguish k-colourable graphs from those that are not (2k-1)-colourable. - 13.01.2026: Recent Developments in Distributed Δ-Coloring, Manuel Jakob, Slides
Abstract
Graph coloring is one of the central problems in distributed computing because it captures the fundamental challenge of symmetry breaking using only local information. In particular, the Δ+1 coloring problem has been extensively studied, as it can still be solved greedily in a centralized setting. While a Δ+1 coloring can be computed in log*(n) rounds in the LOCAL model on constant-degree graphs, the closely related Δ-coloring problem is significantly more challenging. The Δ-coloring problem admits an Ω(log n) round lower bound, established in [BFHKLRSU, STOC'16].
For many years, the algorithm of [Ghaffari, Hirvonen, Kuhn, Maus, PODC'18] was the best known algorithm, leaving a gap to the known lower bound for constant-degree graphs. Recently, this gap has begun to close. First, [Bourreau, Brandt, Nolin, STOC'25] introduced the first algorithm improving upon this result, achieving a log(n)log*(n)-round algorithm. Shortly thereafter, [Jakob, Maus, PODC'25] introduced a log(n)-round algorithm for locally dense graphs with constant degree, and [Bourreau, Brandt, Nolin, SODA'25] obtained a log(n)-round algorithm for general constant-degree graphs.- This talk presents these recent breakthroughs and the techniques that have led to significant improvements in algorithms for Δ-coloring.
-
20.10.2025: Towards Optimal Distributed Edge Coloring with Fewer Colors, Florian Schager, Slides
Abstract
There is a huge difference in techniques and runtimes of distributed algorithms for problems that
can be solved by a sequential greedy algorithm and those that cannot. A prime example of this
contrast appears in the edge coloring problem: while (2∆ − 1)-edge coloring—where ∆ is the
maximum degree—can be solved in O(log∗(n)) rounds on constant-degree graphs, the seemingly
minor reduction to (2∆ − 2) colors leads to an Ω(log n) lower bound [Chang, He, Li, Pettie & Uitto,
SODA’18]. Understanding this sharp divide between very local problems and inherently more global
ones remains a central open question in distributed computing and it is a core focus of this paper.
As our main contribution we design a deterministic distributed O(log n)-round reduction from
the (2∆−2)-edge coloring problem to the much easier (2∆−1)-edge coloring problem. This reduction
is optimal, as the (2∆ − 2)-edge coloring problem admits an Ω(log n) lower bound that even holds
on the class of constant-degree graphs, whereas the 2∆ − 1-edge coloring problem can be solved
in O(log∗ n) rounds. By plugging in the (2∆ − 1)-edge coloring algorithms from [Balliu, Brandt,
Kuhn & Olivetti, PODC’22] running in O(log12 ∆ + log∗ n) rounds, we obtain an optimal runtime of
O(log n) rounds as long as ∆ = 2O(log1/12 n). Previously, such an optimal algorithm was only known
for the class of constant-degree graphs [Brandt, Maus, Narayanan, Schager & Uitto, SODA’25].
Furthermore, on general graphs our reduction improves the runtime from ˜O(log3 n) to ˜O(log5/3 n).
In addition, we also obtain an optimal O(log log n)-round randomized reduction of (2∆ − 2)-edge
coloring to (2∆ − 1)-edge coloring. This leads to a ˜O(log5/3 log n)-round (2∆ − 2)-edge coloring
algorithm, which beats the (very recent) previous state-of-the-art taking ˜O(log8/3 log n) rounds from
[Bourreau, Brandt & Nolin, STOC’25].
Lastly, we obtain an O(log∆ n)-round reduction from the (2∆ − 1)-edge coloring, albeit to the
somewhat harder maximal independent set (MIS) problem. -
13.10.2025: Classical Simulation of Quantum CSP Strategies, Demian Banakh
Abstract
In this talk, I will first introduce the two-prover 1-round games. Then I will describe different classical and quantum strategies, and the advantage that the provers gain in the respective scenarios. Finally, I present a proof that any perfect quantum strategy for the two-prover game encoding a constraint satisfaction problem (CSP) can be simulated via a perfect classical strategy with an extra classical communication channel, whose size depends only on the size of the shared quantum system, and structural parameters of the CSP template. A byproduct of this result is that the gap between the classical chromatic number of graphs and its quantum variant is bounded whenever the size of the shared quantum system is bounded. -
24.09.2025: A Simple Algorithm for Trimmed Multipoint Evaluation, Leo Wennmann
Abstract
Evaluating a polynomial on a set of points is a fundamental task in computer algebra. In this work, we revisit a particular variant called trimmed multipoint evaluation: given an n-variate polynomial with bounded individual degree d and total degree D, the goal is to evaluate it on a natural class of input points. This problem arises as a key subroutine in recent algorithmic results [Dinur; SODA ’21], [Dell, Haak, Kallmayer, Wennmann; SODA ’25]. It is known that trimmed multipoint evaluation can be solved in near-linear time [van der Hoeven, Schost; AAECC ’13] by a clever yet somewhat involved algorithm. We present a simple recursive algorithm that avoids heavy computer-algebraic machinery and can be readily understood by researchers without specialized background. -
18.09.2025: Edge densities of drawings of graphs with one forbidden cell, Benedikt Hahn
Abstract
A connected topological drawing of a graph divides the plane into a number of cells. The type of a cell c is the cyclic sequence of crossings and vertices along the boundary walk of c. For example, all triangular cells with three incident crossings and no incident vertex share the same cell type. When a simple drawing of an n-vertex multigraph G does not contain any such cells, Ackerman and Tardos [JCTA 2007] proved that G has at most 8n-20 edges and gave a lower bound construction with 7n-30 edges. We initiate the in-depth study of drawings that do not contain one fixed cell type \mathfrak{c}, and investigate the edge density of the corresponding graphs, i.e., the maximum possible number of edges. With one exception, we show for every cell type \mathfrak{c} that the maximum edge density of n-vertex (multi)graphs of \mathfrak{c}-free drawings grows either linear or quadratic in n. In most cases, our bounds are tight up to additive constants. This presentation is based on joint work with Torsten Ueckerdt and Birgit Vogtenhuber which I will present the following week at GD. The conference paper can be found at [https://arxiv.org/abs/2508.16368](https://arxiv.org/abs/2508.16368). -
18.08.2025: On the geometric k-colored crossing number of K_n, Benedikt Hahn
Abstract
Given a graph G, the geometric k-colored crossing number cr_k(G) is the smallest number of monochromatic crossings in any k-edge-colored straight-line drawing of G. For small k, we improve asymptotic upper bounds on cr_k(K_n) by developing a procedure that derives k-edge colored drawings of K_n for arbitrary n from an initial drawing with few monochromatic crossings. This presentation is based on joint work with Bettina Klinz and Birgit Vogtenhuber which I will present the following week at Eurocomb. The submitted paper can be found at [https://arxiv.org/abs/2505.18014](https://arxiv.org/abs/2505.18014). -
21.07.2025: Drainability and Fillability of Polyominoes in Models of Global Control, Peter Kramer
Abstract
We study the question of draining and filling geometric shapes using global control: Given a board, defined as a subset of the square grid as well as a number of “infill points” (sources), the question is whether, and if so how, the entire board can be filled by adding particles through the set of sources, with all particles moving in the same direction as determined by global control mechanisms. - 16.07.2025: Total Coloring in Distributed Computing, Armand Ledoux
-
16.06.2025: A framework for boosting maximum matching approximation, Slobodan Mitrovic
Abstract
I will present a framework for improving the approximation guarantees of maximum matching algorithms using access to a constant-factor approximation maximum matching oracle. The framework applies across several models, including massively parallel, distributed, and dynamic settings. I will first outline a semi-streaming algorithm that serves as the foundation for our approach. Building on this, I will describe how to obtain a general boosting framework that adaptively invokes the oracle on small subgraphs and can be implemented efficiently in a range of computational models. In the static setting, we show how to simulate key primitives from the semi-streaming algorithm by reducing them to a small number of approximate matching calls on carefully constructed subgraphs. A crucial observation is that the size of these matchings and subgraphs decreases rapidly, enabling a fast and efficient boosting framework. In the dynamic setting, we cannot construct these subgraphs explicitly, so we instead sample small vertex sets and apply the oracle to their induced subgraphs. These are then passed to existing frameworks for dynamic matching. I will outline the main challenges in sampling such induced subgraphs and explain how we address them. This presentation is based on works https://arxiv.org/abs/2106.04179, https://arxiv.org/abs/2412.19057, and https://arxiv.org/abs/2503.01147. -
02.06.2025: Nearly-Optimal Distributed Ruling Sets for Trees and high-girth graphs, Malte Baumecker
Abstract
Given a graph G=(V,E), a \beta-ruling set is a subset S\subseteq V that is i) independent, and ii) every node v\in V has a node of S within distance \beta. In this paper we present almost optimal distributed algorithms for finding ruling sets in trees and high girth graphs in the classic LOCAL model. As our first contribution we present an O(\log\log n)-round randomized algorithm for computing 2-ruling sets on trees, almost matching the \Omega(\log\log n/\log\log\log n) lower bound given by Balliu et al. [FOCS'20]. Second, we show that 2-ruling sets can be solved in \widetilde{O}(\log^{5/3}\log n) rounds in high-girth graphs. Lastly, we show that O(\log\log\log n)-ruling sets can be computed in \widetilde{O}(\log\log n) rounds in high-girth graphs matching the lower bound up to triple-log factors. All of these results either improve polynomially or exponentially on the previously best algorithms and use a smaller domination distance \beta. -
19.05.2025: Coordinated Motion Planning in Bounded Domains, Peter Kramer
Abstract
We study the problem of Multi-Agent Path Finding (MAPF) for labeled agents within a simply connected domain. Each agent has a unique start and target position, and the goal is to compute a sequence of parallel, collision-free movements that minimizes the total time (makespan) required for all agents to reach their targets. Our focus is on densely packed agents within a simple polyomino—a union of axis-aligned unit squares with integer coordinates. This dense setup limits agent mobility and demands complex motion coordination. Highlights of our results include: 1. A characterization of polyominoes where reconfiguration is always possible. 2. Identification of shape parameters that define worst-case makespan bounds. 3. Algorithms achieving asymptotically optimal performance, even in highly constrained settings. These findings build on and extend previous work by Demaine et al. (_SIAM J. Comput._, 2019) and Alpert et al. (_Computational Geometry_, 2022) on motion planning in structured grid environments. -
24.04.2025: Distributed Interactive Proofs, Yuval Gil
Abstract
We provide new distributed interactive proofs (DIP) for planarity and related graph families. The notion of a _distributed interactive proof_ (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In this setting, the verifier consists of n nodes connected by a communication graph G. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph G satisfies a certain property (e.g., planarity) in a small number of rounds, and with a small communication bound, denoted as the _proof size_. Prior work by Naor, Parter and Yogev (SODA 2020) presented a DIP for planarity that uses three interaction rounds and a proof size of O(log n). Feuilloley et al. (PODC 2020) showed that the same can be achieved with a single interaction round and without randomization, by providing a proof labeling scheme with a proof size of O(log n). In a subsequent work, Bousquet, Feuilloley, and Pierron (OPODIS 2021) achieved the same bound for related graph families such as outerplanarity, series-parallel graphs, and graphs of treewidth at most 2. In this work, we design new DIPs that use exponentially shorter proofs compared to the state-of-the-art bounds. Our main results are: - There is a 5-round protocol with O(log log n) proof size for outerplanarity. - There is a 5-round protocol with O(log log n) proof size for verifying embedded planarity and O(log log n+log Δ) proof size for general planar graphs, where Δ is the maximum degree in the graph. In the former setting, it is assumed that an embedding of the graph is given (e.g., each node holds a clockwise orientation of its neighbors) and the goal is to verify that it is a valid planar embedding. The latter result should be compared with the non-interactive setting for which there is lower bound of Ω(log n) bits for graphs withΔ=O(1) by Feuilloley et al. (PODC 2020). - The non-interactive deterministic lower bound of Ω(log n) bits by Feuilloley et al. (PODC 2020) can be extended to hold even if the verifier is randomized. Moreover, the lower bound holds even with the assumption that the verifier's randomness comes in the form of an unbounded random string _shared_ among the nodes. We also show that our DIPs can be extended to protocols with similar bounds for verifying series-parallel graphs and graphs with tree-width at most 2. Perhaps surprisingly, our results demonstrate that the key technical barrier for obtaining o(log log n) labels for all our problems is a basic sorting verification task in which all nodes are embedded on an oriented path P⊆G and it is desired for each node to distinguish between its left and right G-neighbors. Based on joint work with Merav Parter. -
07.04.2025: Deterministic Online Bipartite Edge Coloring, Joakim Blikstad
Abstract
We study online bipartite edge coloring, with nodes on one side of the graph revealed sequentially. The trivial greedy algorithm is (2 — _o_ (1))-competitive, which is optimal for graphs of low maximum degree, Δ = _O_ (log n) [BNMN IPL’92]. Numerous online edge-coloring algorithms outperforming the greedy algorithm in various settings were designed over the years (e.g., [AGKM FOCS’03, BMM SODA’10, CPW FOCS’19, BGW SODA’21, KLSST STOC’22, BSVW STOC’24]), all crucially relying on randomization. A commonly- held belief, first stated by [BNMN IPL’92], is that randomization is necessary to outperform greedy. We refute this belief. We present a _deterministic_ algorithm that beats greedy for sufficiently large Δ = Ω(log _n_ ), and in particular has competitive ratio e/(e-1) + o(1) for all Δ = _ω_ (log _n_ ). We obtain our result via a new simple _randomized_ algorithm that works against _adaptive adversaries_ (as opposed to oblivious adversaries assumed by prior work). This implies the existence of a similarly-competitive deterministic algorithm [BDBKTW STOC’90]. A key ingredient in our algorithm (and the reason for its competitive ratio) is the use of contention resolution schemes of [FV FOCS’06]. This is the first use of contention resolution schemes, which are randomized algorithms for randomized inputs, that yields a deterministic algorithm for deterministic settings. -
12.03.2025: Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time, Leo Wennmann
Abstract
In this work we revisit the elementary scheduling problem 1| |∑pjUj. The goal is to select, among n jobs with processing times and due dates, a subset of jobs with maximum total processing time that can be scheduled in sequence without violating their due dates. This problem is NP-hard, but a classical algorithm by Lawler and Moore from the 60s solves this problem in pseudo-polynomial time O(nP), where P is the total processing time of all jobs. With the aim to develop best-possible pseudo-polynomial-time algorithms, a recent wave of results has improved Lawler and Moore's algorithm for 1| |∑pjUj: First to time O~(P7/4) [Bringmann, Fischer, Hermelin, Shabtay, Wellnitz; ICALP'20], then to time O~(P5/3) [Klein, Polak, Rohwedder; SODA'23], and finally to time O~(P7/5) [Schieber, Sitaraman; WADS'23]. It remained an exciting open question whether these works can be improved further. In this work we develop an algorithm in near-linear time O~(P) for the 1||∑pjUj problem. This running time not only significantly improves upon the previous results, but also matches conditional lower bounds based on the Strong Exponential Time Hypothesis or the Set Cover Hypothesis and is therefore likely optimal (up to subpolynomial factors). Our new algorithm also extends to the case of m machines in time O~(Pm). In contrast to the previous improvements, we take a different, more direct approach inspired by the recent reductions from Modular Subset Sum to dynamic string problems. We thereby arrive at a satisfyingly simple algorithm. - 03.02.2025: The Laplacian Paradigm in Distributed Models, Tijn de Vos
- 20.01.2025: A universal planar graph for trees, Joachim Orthaber
-
09.12.2024: On the Locality of Hall's Theorem, Florian Schager, Slides
Abstract
The last five years of research on distributed graph algorithms have seen huge leaps of progress, both regarding algorithmic improvements and impossibility results: new strong lower bounds have emerged for many central problems and exponential improvements over the state of the art have been achieved for the runtimes of many algorithms. Nevertheless, there are still large gaps between the best known upper and lower bounds for many important problems. The current lower bound techniques for deterministic algorithms are often tailored to obtaining a logarithmic bound and essentially cannot be used to prove lower bounds beyond \Omega(\log n). In contrast, the best deterministic upper bounds are often polylogarithmic, raising the fundamental question of how to resolve the gap between logarithmic lower and polylogarithmic upper bounds and finally obtain tight bounds. We develop a novel algorithm design technique aimed at closing this gap. In essence, each node finds a carefully chosen local solution in O(\log n) rounds and we guarantee that this solution is consistent with the other nodes' solutions without coordination. The local solutions are based on a distributed version of Hall's theorem that may be of independent interest and motivates the title of this work. We showcase our framework by improving on the state of the art for the following fundamental problems: edge coloring, bipartite saturating matchings and hypergraph sinkless orientation. In particular, we obtain an asymptotically optimal O(\log n)-round algorithm for 3\Delta/2-edge coloring in bounded degree graphs. The previously best bound for the problem was O(\log^4 n) rounds, obtained by plugging in the state-of-the-art maximal independent set algorithm from [arXiv:2303.16043](https://arxiv.org/abs/2303.16043) into the 3\Delta/2-edge coloring algorithm from [arXiv:1711.05469](https://arxiv.org/abs/1711.05469). - 11.11.2024: Tree decompositions and graph decompositions, Benedikt Hahn, Slides
- 04.11.2024: Efficient Route Planning, Manuel Jakob, Slides
- 28.10.2024: Game Theory, Oswin Aichholzer, Slides
Short schedule
- 17.02.2026: Kyungjin Cho
Optimal Algorithm for the Planar Two-Center Problem - 24.02.2026: Kritika Kashyap
- 02.03.2026: TBA
- 09.03.2026: EuroCG talks - Part 1
- 16.03.2026: EuroCG talks - Part 2