"AlgoComp" is a weekly seminar series hosted by the Theoretical Computer Science Section at the IT University of Copenhagen. The seminars take place every Monday and feature presentations by PhD students, postdoctoral researchers, faculty members, and visiting scholars. The scope of the talks covers all topics of algorithms and complexity, and can range from presenting recently published cutting-edge research to informal and open-ended problem sessions. Attendance is open to everyone, including interested bachelor’s and master’s students.
The seminar is currently maintained by Lasse Wulf and Ivor van der Hoog. If you are interested in giving a talk, don't hesistate to contact lasw@itu.dk.
02.02. Sampson Wong KU Copenhagen
title: A well-separated pair decomposition for low density graphs
Abstract: -
09.02. Ivor van der Hoog ITU
title: Simpler optimal sorting from a directed acyclic graph
Abstract: -
16.02. Georg Schindling TU Darmstadt
title: Restricted Requantification and Homomorphism Indistinguishability
Abstract: Finite variable logics play a central role in finite model theory, serving as a foundational framework for analyzing the complexity of finite structures. A combinatorial perspective characterizes equivalence in these logics via homomorphism indistinguishability: for certain graph classes, two graphs agree on all homomorphism counts from the class if and only if they satisfy the same sentences in a corresponding logic. This viewpoint often reveals connections between structural properties of graph classes and the expressive power of logical fragments. We extend this perspective to logics with restricted requantification, thereby refining the stratification of syntactic resources in finite variable counting logics. By parameterizing the number of requantifiable variables, we obtain distinct logical fragments and investigate their interaction with homomorphism counts and computational complexity.
23.02. Peter Kramer TU Braunschweig
title: Coordinated motion planning using robots
02.03. Amir Nikahadi ITU
title: On the longest path transversal number
Abstract: -
09.03. Niels I. Christiansen DTU
title: 3-connectivity for 2-connected graphs in O(log n) time per operation using SPQR trees
Abstract: -
16.03. Sarita De Berg ITU
title: The Contiguous Art Gallery Problem is in $\Theta(n\log n)$
Abstract: Recently, a natural variant of the Art Gallery problem, known as the Contiguous Art Gallery problem, was proposed. Given a simple polygon $P$, the goal is to partition its boundary $\partial P$ into the smallest number of contiguous segments such that each segment is completely visible from some point in~$P$ (the guard). Unlike the classical Art Gallery problem, which is NP-hard, this variant is polynomial-time solvable.
At SoCG 2025, three independent works presented algorithms for this problem, each achieving a running time of $O(k n^5 \log n)$ (or $O(n^6\log n)$), where $k$ is the size of an optimal solution. Interestingly, these results were obtained using entirely different approaches, yet all led to roughly the same asymptotic complexity, suggesting that such a running time might be inherent to the problem.
We show that this is not the case. We present an $O(n \log n)$-time algorithm, achieving an $O(k n^4)$ factor speed-up over the previous state-of-the-art. We also give a straightforward lower bound reduction from the set intersection problem. We thus show that the Contiguous Art Gallery problem is in $\Theta(n \log n)$.
23.03. Lasse Wulf ITU Time changed to 12.15am!
title: Exact Matching. Recent progress and open questions
Abstract: The Exact matching problem is an infamous problem for which we know a randomized poly-time algorithm since 1987, but finding a deterministic counterpart has evaded the research community for almost 40 years. Formally stated, we are given a bipartite graph, whose edges are 0-1 weighted, and some number k. The question is if there exists a perfect matching of weight exactly equal to k. In this talk, I will highlight some of my own research, which achieves deterministic (combinatorial) algorithms for special restricted graph classes, or deterministic approximations. I also highlight interesting open questions, that may be easier to achieve than tackling the full problem.
30.03. Easter break
title: TBA
Abstract: -
06.04 Easter break
title: TBA
Abstract: -
13.04 Prateek Dviwedi ITU
title: TBA
Abstract: -
20.04 TBA
title: TBA
Abstract: -
27.04 Michal Feldman Tel Aviv University
title: TBA
Abstract: -
04.05 TBA
title: TBA
Abstract: -
11.05 TBA
title: TBA
Abstract: -