# Dr. Martin Schirneck

I recently moved to a new research group:

**Theory and Application of Algorithms**

University of Vienna

You can reach me there via martin.schirneck(at)univie.ac.at.

## Research Interests

My research interests include various topics in mathematics and theoretical computer science.

I am currently working on the following subjects.

- fault-tolerant data structures
- data profiling
- enumeration algorithms and complexity
- parameterized complexity
- evolutionary computation and black-box complexity

I have been involved in past and ongoing research projects in the Algorithm Engineering group. These projects include scientific work with our students as well as collaborations with partners in industry.

- Distributed Evolutionary Search & Theory of Crossover-Based Optimization
- Fault Tolerant Algorithms
- Enumeration in Data Profiling
- Lossy Compression of Time Series Data

A short CV can be found here.

## Talks

In October 2018, I was invited to the Dagstuhl seminar on Algorithmic Enumeration to give a talk about *Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling* (slides).

I also had the opportunity to present my work at the Friedrich Schiller University Jena, the University of Glasgow, as well as the Humboldt University and Technical University Berlin. My contributed talks include presentations at ALENEX, ALT, ESA, FOGA, GECCO, IPEC, ITCS, MFCS, STACS, STOC, VLDB, and WEPA.

My ESA, ITCS, and STOC talks are available online.

## Teaching

### As Advisor

- Bachelor thesis of Marc Dollmann, Winter 2022/23 (University of Vienna)
*Graph Clustering: A Comparison of Louvain and Leiden* - Master thesis of Simon Wietheger, Winter 2022/23
*Fair Correlation Clustering in Forests* - Theory of Crossover-Based Optimization, Winter 2021/22
- Fault Tolerant Algorithms, Summer 2021
- Master thesis of Benjamin Feldmann, Winter 2019/20
*Distributed Unique Column Combinations Discovery* - Bachelor thesis of Linus Heinzl, Summer 2019
*Analysis of the Parameter Configuration of the Ramer-Douglas-Peucker Algorithm for Time Series Compression* - Bachelor thesis of Felix Mujkanovic, Summer 2019
*Explaining the Predictions of Any Time Series Classifier* - Lossy Compression of Time Series Data, Year 2018/19
- Bachelor thesis of Julius Lischeid, Summer 2018
*Lexicographic Enumeration of Hitting Sets in Hypergraphs* - Master thesis of Philipp Fischbeck, Winter 2017/18
*On the Effectiveness of Data Reduction for Covering Problems in Real-World Transit Networks* - Distributed Evolutionary Search, Winter 2016/17

### As Guest Lecturer

- Teaching Scientific Writing, Summer 2021
- Data Profiling, Winter 2020/21
*Discovery of Unique Column Combinations via Hitting Sets*

### As Teaching Assistant

- Theorie der Künstlichen Intelligenz, Winter 2020/21
- Wahrscheinlichkeitstheorie, Summer 2020
- Theorie der Künstlichen Intelligenz, Winter 2019/20
- Wahrscheinlichkeitstheorie, Summer 2018
- Wahrscheinlichkeitstheorie, Summer 2017
- Algorithmic Hits of the 80s and 90s, Winter 2016/17
- Randomisierte Algorithmen II, Winter 2016/17
- Randomisierte Algorithmen, Summer 2016
- Algorithmic Gems, Summer 2016

## Other Activities

In the Algorithm Engineering group, I am one of the mentors to the new members. I also maintain the group's news feed (RSS) and do some of the TYPO3 content management on our sites. Besides my studies, I try to increase article quality in the German Wikipedia, especially in the math and CS section.

In 2015, I was a tutor at the HPI Schülerkolleg teaching school children basic computer science.

I played Go as a member of the team Jena III in the German Bundesliga in the 2014/15 season.

- Bilò, Davide; Chechik, Shiri; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin
**Approximate Distance Sensitivity Oracles in Subquadratic Space**TheoretiCS 2024 - Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin
**Fault-Tolerant ST-Diameter Oracles**International Colloquium on Automata, Languages and Programming (ICALP) 2023: 24:1–24:20 - Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin
**Compact Distance Oracles with Large Sensitivity and Low Stretch**Algorithms and Data Structures Symposium (WADS) 2023: 149–163 - Casel, Katrin; Friedrich, Tobias; Schirneck, Martin; Wietheger, Simon
**Fair Correlation Clustering in Forests**Foundations of Responsible Computing (FORC) 2023: 9:1–9:12 - Bilò, Davide; Chechik, Shiri; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, Martin
**Approximate Distance Sensitivity Oracles in Subquadratic Space**Symposium on Theory of Computing (STOC) 2023: 1396–1409 - Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon
**Crossover for Cardinality Constrained Optimization**ACM Transactions on Evolutionary Learning and Optimization 2023: 1–32 - Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin
**Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances**International Colloquium on Automata, Languages and Programming (ICALP) 2022: 68:1–68:19 - Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, Simon
**Crossover for Cardinality Constrained Optimization**Genetic and Evolutionary Computation Conference (GECCO) 2022: 1399–1407Best Paper Award (Theory Track) - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Complexity of Dependency Detection and Discovery in Relational Databases**Theoretical Computer Science 2022: 79–96 - Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, Simon
**Fixed-Parameter Sensitivity Oracles**Innovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18 - Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin
**Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling**Journal of Computer and System Sciences 2022: 192–213 - Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin
**Space-Efficient Fault-Tolerant Diameter Oracles**Mathematical Foundations of Computer Science (MFCS) 2021: 18:1–18:16 - Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin
**Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles**European Symposium on Algorithms (ESA) 2021: 18:1–18:17 - Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank
**Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints**Algorithmica 2020: 3117–3123 - Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin
**Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints**Theoretical Computer Science 2020: 3–19 - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Minimization of Random Hypergraphs**European Symposium on Algorithms (ESA) 2020: 21:1–21:15 - Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, Martin
**Hitting Set Enumeration with Partial Information for Unique Column Combination Discovery**Proceedings of the VLDB Endowment 2020: 2270–2283 - Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin
**Efficiently Enumerating Hitting Sets of Hypergraphs Arising in Data Profiling**Algorithm Engineering and Experiments (ALENEX) 2019: 130–143 - Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, Martin
**Understanding the Effectiveness of Data Reduction in Public Transportation Networks**Workshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101 - Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank
**Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints**Algorithmica 2019: 828–857 - Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin
**Island Models Meet Rumor Spreading**Algorithmica 2019: 886–915 - Kötzing, Timo; Schirneck, Martin; Seidel, Karen
**Normal Forms in Semantic Language Identification**Algorithmic Learning Theory (ALT) 2017: 493–516 - Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, Frank
**Reoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints**Genetic and Evolutionary Computation Conference (GECCO) 2017: 1407–1414 - Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, Martin
**Island Models Meet Rumor Spreading**Genetic and Evolutionary Computation Conference (GECCO) 2017: 1359–1366 - Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, Martin
**Analysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear Constraints**Foundations of Genetic Algorithms (FOGA) 2017: 45–54 - Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin
**The Parameterized Complexity of Dependency Detection in Relational Databases**International Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1–6:13 - Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, Martin
**Fast Building Block Assembly by Majority Vote Crossover**Genetic and Evolutionary Computation Conference (GECCO) 2016: 661–668 - Kötzing, Timo; Schirneck, Martin
**Towards an Atlas of Computational Learning Theory**Symposium on Theoretical Aspects of Computer Science (STACS) 2016: 47:1–47:13

## Theses

- Schirneck, Martin
**Enumeration Algorithms in Data Profiling**PhD Thesis, Hasso Plattner Institute, University of Potsdam 2022 - Schirneck, Martin
**On Restrictions in Computational Language Learning**Master Thesis, Friedrich Schiller University Jena 20152016 Dean's Prize for Best Thesis (Examenspreis des Dekans). - Schirneck, Martin
**Betrachtungen über ein distanzbasiertes Klassifikationsverfahren**Bachelor Thesis, Friedrich Schiller University Jena 2012