Martin Schirneck

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.

• STOC 2023 Approximate Distance Sensitivity Oracles in Subquadratic Space (slides)
• ITCS 2022 Fixed-Parameter Sensitivity Oracles (slides)
• ESA 2021 Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles (slides)
• ESA 2020 The Minimization of Random Hypergraphs (slides)

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.

Publications

A list of my publications can be found here and on DBLP.

•  

  Bilò, Davide; Chechik, Shiri; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, MartinApproximate Distance Sensitivity Oracles in Subquadratic SpaceTheoretiCS 2024

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, MartinFault-Tolerant ST-Diameter OraclesInternational Colloquium on Automata, Languages and Programming (ICALP) 2023: 24:1–24:20

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, MartinCompact Distance Oracles with Large Sensitivity and Low StretchAlgorithms and Data Structures Symposium (WADS) 2023: 149–163

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Casel, Katrin; Friedrich, Tobias; Schirneck, Martin; Wietheger, SimonFair Correlation Clustering in ForestsFoundations of Responsible Computing (FORC) 2023: 9:1–9:12

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Chechik, Shiri; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Krogmann, Simon; Schirneck, MartinApproximate Distance Sensitivity Oracles in Subquadratic SpaceSymposium on Theory of Computing (STOC) 2023: 1396–1409

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, SimonCrossover for Cardinality Constrained OptimizationACM Transactions on Evolutionary Learning and Optimization 2023: 1–32

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Schirneck, MartinDeterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs DistancesInternational Colloquium on Automata, Languages and Programming (ICALP) 2022: 68:1–68:19

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Kötzing, Timo; Radhakrishnan, Aishwarya; Schiller, Leon; Schirneck, Martin; Tennigkeit, Georg; Wietheger, SimonCrossover for Cardinality Constrained OptimizationGenetic and Evolutionary Computation Conference (GECCO) 2022: 1399–1407

  Best Paper Award (Theory Track)

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Complexity of Dependency Detection and Discovery in Relational DatabasesTheoretical Computer Science 2022: 79–96

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Casel, Katrin; Choudhary, Keerti; Cohen, Sarel; Friedrich, Tobias; Lagodzinski, J.A. Gregor; Schirneck, Martin; Wietheger, SimonFixed-Parameter Sensitivity OraclesInnovations in Theoretical Computer Science (ITCS) 2022: 23:1–23:18

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingJournal of Computer and System Sciences 2022: 192–213

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, MartinSpace-Efficient Fault-Tolerant Diameter OraclesMathematical Foundations of Computer Science (MFCS) 2021: 18:1–18:16

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, MartinNear-Optimal Deterministic Single-Source Distance Sensitivity OraclesEuropean Symposium on Algorithms (ESA) 2021: 18:1–18:17

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankCorrection to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica 2020: 3117–3123

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, MartinAnalysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear ConstraintsTheoretical Computer Science 2020: 3–19

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Minimization of Random HypergraphsEuropean Symposium on Algorithms (ESA) 2020: 21:1–21:15

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Birnick, Johann; Bläsius, Thomas; Friedrich, Tobias; Naumann, Felix; Papenbrock, Thorsten; Schirneck, MartinHitting Set Enumeration with Partial Information for Unique Column Combination DiscoveryProceedings of the VLDB Endowment 2020: 2270–2283

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, MartinEfficiently Enumerating Hitting Sets of Hypergraphs Arising in Data ProfilingAlgorithm Engineering and Experiments (ALENEX) 2019: 130–143

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Schirneck, MartinUnderstanding the Effectiveness of Data Reduction in Public Transportation NetworksWorkshop on Algorithms and Models for the Web Graph (WAW) 2019: 87–101

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankReoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsAlgorithmica 2019: 828–857

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, MartinIsland Models Meet Rumor SpreadingAlgorithmica 2019: 886–915

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Kötzing, Timo; Schirneck, Martin; Seidel, KarenNormal Forms in Semantic Language IdentificationAlgorithmic Learning Theory (ALT) 2017: 493–516

  [ ][ ][ URL ][ Download ]

•  

  Shi, Feng; Schirneck, Martin; Friedrich, Tobias; Kötzing, Timo; Neumann, FrankReoptimization Times of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform ConstraintsGenetic and Evolutionary Computation Conference (GECCO) 2017: 1407–1414

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Doerr, Benjamin; Fischbeck, Philipp; Frahnow, Clemens; Friedrich, Tobias; Kötzing, Timo; Schirneck, MartinIsland Models Meet Rumor SpreadingGenetic and Evolutionary Computation Conference (GECCO) 2017: 1359–1366

  [ ][ ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Kötzing, Timo; Lagodzinski, J. A. Gregor; Neumann, Frank; Schirneck, MartinAnalysis of the (1+1) EA on Subclasses of Linear Functions under Uniform and Linear ConstraintsFoundations of Genetic Algorithms (FOGA) 2017: 45–54

  [ ][ ][ DOI ][ Download ]

•  

  Bläsius, Thomas; Friedrich, Tobias; Schirneck, MartinThe Parameterized Complexity of Dependency Detection in Relational DatabasesInternational Symposium on Parameterized and Exact Computation (IPEC) 2016: 6:1–6:13

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Friedrich, Tobias; Kötzing, Timo; Krejca, Martin S.; Nallaperuma, Samadhi; Neumann, Frank; Schirneck, MartinFast Building Block Assembly by Majority Vote CrossoverGenetic and Evolutionary Computation Conference (GECCO) 2016: 661–668

  [ ][ ][ URL ][ DOI ][ Download ]

•  

  Kötzing, Timo; Schirneck, MartinTowards an Atlas of Computational Learning TheorySymposium on Theoretical Aspects of Computer Science (STACS) 2016: 47:1–47:13

  [ ][ ][ URL ][ DOI ][ Download ]

Theses

•  

  Schirneck, MartinEnumeration Algorithms in Data ProfilingPhD Thesis, Hasso Plattner Institute, University of Potsdam 2022

  [ ][ ][ Download ]

•  

  Schirneck, MartinOn Restrictions in Computational Language LearningMaster Thesis, Friedrich Schiller University Jena 2015

  2016 Dean's Prize for Best Thesis (Examenspreis des Dekans).

  [ ][ ][ Download ]

•  

  Schirneck, MartinBetrachtungen über ein distanzbasiertes KlassifikationsverfahrenBachelor Thesis, Friedrich Schiller University Jena 2012

  [ ][ ][ Download ]