Martin Schirneck
Postdoctoral Researcher
Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics
| martin.schirneck@kit.edu | |
| office | Computer Science building 50.34: Room 308 |
| office hours | I am best reached via email. You can also just drop by my office anytime, but I am not always around. |
I am the PI of a research project on the Design, Analysis, and Engineering of Enumeration Algorithms funded by the German Research Foundation (“DFG Eigene Stelle”). Enumeration is the task of computing and listing all solution to a combinatorial problem. The most important problem in enumeration is the generation of all minimal hitting sets of a hypergraph, known as the Transversal Hypergraph. In this project, I explore the combinatorics of finite sets to find new classes for which the Transversal Hypergraph problem is tractable. The resulting enumeration algorithms have applications in artificial intelligence and data profiling.
Research Interests
My research interests include various topics in mathematics and theoretical computer science. I have contributed to the following topics.
- enumeration algorithms and complexity
- data profiling
- fault-tolerant data structures
- parameterized and fine-grained complexity
- evolutionary computation and randomized search heuristics
- time series classification
- algorithmic learning theory
A short CV can be found here.
(Co-)Supervised Theses and Projects
I have been fortunate to work with several outstanding students.
Master Theses
- Simon Wietheger, Winter 2022/23 (HPI): Fair Correlation Clustering in Forests, appeared at FORC 2023
- Benjamin Feldmann, Winter 2019/20 (HPI): Distributed Unique Column Combinations Discovery
- Philipp Fischbeck, Winter 2017/18 (HPI): On the Effectiveness of Data Reduction for Covering Problems in Real-World Transit Networks, appeared at WAW 2019
Bachelor Theses
- Bennet Hörmann, Winter 2025/26: A Lower Bound on Minimal-to-Maximal Conversion Search
- Marc Dollmann, Winter 2022/23 (U Vienna): Graph Clustering: A Comparison of Louvain and Leiden
- Linus Heinzl, Summer 2019 (HPI): Analysis of the Parameter Configuration of the Ramer-Douglas-Peucker Algorithm for Time Series Compression
- Felix Mujkanovic, Summer 2019 (HPI): Explaining the Predictions of Any Time Series Classifier
- Julius Lischeid, Summer 2018 (HPI): Lexicographic Enumeration of Hitting Sets in Hypergraphs, appeared at ALENEX 2019 and JCSS 2022
Student Projects
- Muhammad Raza Ali, Winter 2024/25 (U Vienna): Parallelizing Hitting Set Enumeration Algorithms for Data Profiling
- Winter 2021/22 (HPI): Theory of Crossover-Based Optimization, received a Best Paper Award at GECCO 2022 and appeared at TELO 2023
- Summer 2021 (HPI): Fault Tolerant Algorithms, appeared at ITCS 2022
- Academic Year 2018/19 (HPI): Lossy Compression of Time Series Data
Talks
Some of my conference talks are available online.
- ITCS 2022: Fixed-Parameter Sensitivity Oracles (slides)
- ESA 2020: The Minimization of Random Hypergraphs (slides)
Publications
2025
Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks.
AAAI Conference on Artificial Intelligence (AAAI) 2025
2024
Discovering Functional Dependencies through Hitting Set Enumeration.
Proceedings of the ACM on Management of Data 2024
Approximate Distance Sensitivity Oracles in Subquadratic Space.
TheoretiCS 2024
Improved Distance (Sensitivity) Oracles with Subquadratic Space.
IEEE Annual Symposium on Foundations of Computer Science (FOCS) 2024
2023
Crossover for Cardinality Constrained Optimization.
ACM Transactions on Evolutionary Learning and Optimization 2023
Fair Correlation Clustering in Forests.
Symposium on Foundations of Responsible Computing (FORC) 2023
Fault-Tolerant ST-Diameter Oracles.
International Colloquium on Automata, Languages and Programming (ICALP) 2023
Approximate Distance Sensitivity Oracles in Subquadratic Space.
Symposium on the Theory of Computing (STOC) 2023
Compact Distance Oracles with Large Sensitivity and Low Stretch.
International Symposium on Algorithms and Data Structures (WADS) 2023
2022
Enumeration algorithms in data profiling.
University of Potsdam, Germany 2022
Efficiently enumerating hitting sets of hypergraphs arising in data profiling.
Journal of Computer and System Sciences (JCSS) 2022
The complexity of dependency detection and discovery in relational databases.
Theoretical Computer Science 2022
Crossover for cardinality constrained optimization.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2022
Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances.
International Colloquium on Automata, Languages and Programming (ICALP) 2022
Fixed-Parameter Sensitivity Oracles.
Innovations in Theoretical Computer Science (ITCS) 2022
2021
Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles.
European Symposium on Algorithms (ESA) 2021
Space-Efficient Fault-Tolerant Diameter Oracles.
International Symposium on Mathematical Foundations of Computer Science (MFCS) 2021
2020
Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints.
Algorithmica 2020
Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery.
Proceedings of the VLDB Endowment 2020
Analysis of the (1 + 1) EA on subclasses of linear functions under uniform and linear constraints.
Theoretical Computer Science 2020
The Minimization of Random Hypergraphs.
European Symposium on Algorithms (ESA) 2020
2019
Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints.
Algorithmica 2019
Island Models Meet Rumor Spreading.
Algorithmica 2019
Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2019
Understanding the Effectiveness of Data Reduction in Public Transportation Networks.
Workshop on Algorithms and Models for the Web-Graph (WAW) 2019
2017
Normal Forms in Semantic Language Identification.
International Conference on Algorithmic Learning Theory (ALT) 2017
Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints.
Foundations of Genetic Algorithms (FOGA) 2017
Island models meet rumor spreading.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2017
Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2017
2016
Fast Building Block Assembly by Majority Vote Crossover.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2016
The Parameterized Complexity of Dependency Detection in Relational Databases.
International Symposium on Parameterized and Exact Computation (IPEC) 2016
Towards an Atlas of Computational Learning Theory.
Symposium on Theoretical Aspects of Computer Science (STACS) 2016