Dennis Komm

Last Name

Komm

First Name

Dennis

ORCID

0000-0002-9024-1558

Organisational unit

09779 - Komm, Dennis / Komm, Dennis

Show all metadata

Search Results

Publications 1 - 10 of 13

Wirksamer Informatikunterricht - Eine Einführung
Komm, Dennis (2024)
Unterrichtsqualität: Perspektiven von Expertinnen und Experten ~ Wirksamer Informatikunterricht
Tokenisation over Bounded Alphabets is Hard
Kastreva, Violeta; Whittington, Philip; Komm, Dennis; et al. (2025)
arXiv
Recent works have shown that tokenisation is NP-complete. However, these works assume tokenisation is applied to inputs with unboundedly large alphabets -- an unrealistic assumption, given that in practice tokenisers operate over fixed-size alphabets, such as bytes or Unicode characters. We close this gap by analysing tokenisation over bounded n-ary alphabets, considering two natural variants: bottom-up tokenisation and direct tokenisation, where we must, respectively, select a sequence of merge operations or a vocabulary whose application optimally compresses a dataset. First, we note that proving hardness results for an n-ary alphabet proves the same results for alphabets of any larger size. We then prove that even with binary alphabets, both variants are not only NP-complete, but admit no polynomial-time approximation scheme (unless P=NP). We further show that direct tokenisation remains NP-complete even when applied to unary alphabets. While unary alphabets may not be practically useful, this result establishes that the computational intractability of tokenisation is not an artifact of large alphabets or complex constructions, but a fundamental barrier. Overall, our results explain why practical algorithms such as BPE and UnigramLM are heuristic, and points toward approximation algorithms being an important path going forward for tokenisation research.
Wirksamer Informatikunterricht - Ein Fazit
Komm, Dennis (2024)
Unterrichtsqualität: Perspektiven von Expertinnen und Experten ~ Wirksamer Informatikunterricht
Time-Optimal k-Server
Frei, Fabian; Komm, Dennis; Stocker, Moritz; et al. (2025)
Leibniz International Proceedings in Informatics (LIPIcs) ~ 36th International Symposium on Algorithms and Computation (ISAAC 2025)
The time-optimal k-server problem minimizes the time spent instead of the distance traveled when serving n requests, appearing one after the other, with k servers in a metric space. The classical distance model was motivated by a hard disk with k heads. Instead of minimal head movements, the time model aims for optimal reading speeds. This paper provides a lower bound of 2k-1 on the competitive ratio of any deterministic online algorithm for the time-optimal k-server problem on a specifically designed metric space. This lower bound coincides with the best known upper bound on the competitive ratio for the classical k-server problem, achieved by the famous work function algorithm. We provide further lower bounds of k+1 for all Euclidean spaces and k for uniform metric spaces. Our most technical result, proven by applying Yao’s principle to a suitable instance distribution, is a lower bound of k+H_k-1 that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem, which is polylogarithmic in k. We hope to initiate further intensive study of this natural problem.
Time-Optimal k-Server
Frei, Fabian; Komm, Dennis; Stocker, Moritz; et al. (2025)
arXiv
The time-optimal $k$-server problem minimizes the time spent serving all requests instead of the distances traveled. We give a lower bound of $2k-1$ on the competitive ratio of any deterministic online algorithm for this problem, which coincides with the best known upper bound on the competitive ratio achieved by the work-function algorithm for the classical $k$-server problem. We provide further lower bounds of $k+1$ for all Euclidean spaces and $k$ for uniform metric spaces. For the latter, we give a matching $k$-competitive deterministic algorithm. Our most technical result, proven by applying Yao's principle to a suitable instance distribution on a specifically constructed metric space, is a lower bound of $k+\mathcal{O}(\log k)$ that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem that remains polylogarithmic. With this paper, we hope to initiate a further study of this natural yet neglected problem.
Improving Spatial Abilities
Hauser, Urs; Stern, Elsbeth; Komm, Dennis (2025)
ICER '25: Proceedings of the 2025 ACM Conference on International Computing Education Research V.1
The significance of spatial skills for success in STEM fields has been established through several interdisciplinary studies. In the study presented in this paper, we investigated how comprehensive training in programming using turtle graphics or educational robotics can positively impact high school (MAge = 15.31 years) novices’ spatial skills. In addition, we examined whether prior knowledge (spatial abilities pretest scores), cognitive abilities, math grade, gender, or age explained variation in intervention effects. In a quasi-experimental classroom intervention study with N = 602 students, we differentiated between two experimental groups (turtle graphics and robotics) and a control group studying other CS topics without programming content. Mixed-effects models revealed that turtle programming and robotics training positively improved students’ skills in spatial visualization and spatial orientation. Moreover, female students in the educational robotics group showed significantly greater improvements in their spatial visualization skills than male students.
Online Unbounded Knapsack
Böckenhauer, Hans-Joachim; Gehnen, Matthias; Hromkovič, Juraj; et al. (2025)
Theory of Computing Systems
A survey of online knapsack problems
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Komm, Dennis; et al. (2026)
Discrete Applied Mathematics
We survey the current state of research on the knapsack problem in online and semi-online environments. In particular, we summarize what is known about models where different assumptions commonly made in online computation are relaxed: namely that online algorithms do not know the complete instances they are processing; have to make decisions that are irrevocable; and deal with an input chosen by a malicious adversary.
Forbidden Subgraph Problems with Predictions
Böckenhauer, Hans-Joachim; Jahn, Melvin; Komm, Dennis; et al. (2025)
arXiv
In the Online Delayed Connected H-Node-Deletion Problem, an unweighted graph is revealed vertex by vertex and it must remain free of any induced copies of a specific connected induced forbidden subgraph H at each point in time. To achieve this, an algorithm must, upon each occurrence of H, identify and irrevocably delete one or more vertices. The objective is to delete as few vertices as possible. We provide tight bounds on the competitive ratio for forbidden subgraphs H that do not contain two true twins or that do not contain two false twins. We further consider the problem within the model of predictions, where the algorithm is provided with a single bit of advice for each revealed vertex. These predictions are considered to be provided by an untrusted source and may be incorrect. We present a family of algorithms solving the Online Delayed Connected H-Node-Deletion Problem with predictions and show that it is Pareto-optimal with respect to competitivity and robustness for the online vertex cover problem for 2-connected forbidden subgraphs that do not contain two true twins or that do not contain two false twins, as well as for forbidden paths of length greater than four. We also propose subgraphs for which a better algorithm might exist.
Online Unbounded Knapsack
Böckenhauer, Hans-Joachim; Gehnen, Matthias; Hromkovič, Juraj; et al. (2024)
arXiv
We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and an algorithm has to decide how often to pack each item into a knapsack of bounded capacity. The items are given online and the total size of the packed items must not exceed the knapsack's capacity, while the objective is to maximize the total value of the packed items. While each item can only be packed once in the classical 0-1 knapsack problem, the unbounded version allows for items to be packed multiple times. We show that the simple unbounded knapsack problem, where the size of each item is equal to its value, allows for a competitive ratio of 2. We also analyze randomized algorithms and show that, in contrast to the 0-1 knapsack problem, one uniformly random bit cannot improve an algorithm's performance. More randomness lowers the competitive ratio to less than 1.736, but it can never be below 1.693. In the advice complexity setting, we measure how many bits of information the algorithm has to know to achieve some desired solution quality. For the simple unbounded knapsack problem, one advice bit lowers the competitive ratio to 3/2. While this cannot be improved with fewer than log(n) advice bits for instances of length n, a competitive ratio of 1+epsilon can be achieved with O(log(n/epsilon)/epsilon) advice bits for any epsilon>0. We further show that no amount of advice bounded by a function f(n) allows an algorithm to be optimal. We also study the online general unbounded knapsack problem and show that it does not allow for any bounded competitive ratio for deterministic and randomized algorithms, as well as for algorithms using fewer than log(n) advice bits. We also provide an algorithm that uses O(log(n/epsilon)/epsilon) advice bits to achieve a competitive ratio of 1+epsilon for any epsilon>0.

Publications 1 - 10 of 13

Dennis Komm

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results