Scalable Algorithms (ITI)

Maximilian Katzmann

Postdoctoral Researcher

Karlsruhe Institute of Technology (KIT)
Institute of Theoretical Informatics

email maximilian.katzmann@kit.edu
office Computer Science building 50.34: Room 307
office hours by appointment

Research

I devoted my PhD studies to determining how hyperbolic random graphs can be utilized as a framework for average-case analysis. That is, we looked at graph algorithms that performed significantly better on real-world networks than one would expect when considering their worst-case running times, and used hyperbolic random graphs to model these networks in order to explain the observed phenomena theoretically.

My research interests lie on random graph models that can be used to represent real-world networks and analyzing algorithms on them. In particular, I'm interested in investigating networks with underlying geometry and their connections to real-world graphs, for example in the context of embedding algorithms.

Teaching

Summer 2022:

Summer 2021:

  • Project Seminar: Fault Tolerant Algorithms, Hasso Plattner Institute, Chair for Algorithm Engineering

Winter 2020/2021:

  • Project Seminar: Uncovering Chains of Infection, Hasso Plattner Institute, Chair for Algorithm Engineering

Winter 2018:

  • Algorithmische Geometrie, Hasso Plattner Institute, Chair for Algorithm Engineering (teaching assistant)

Misc:

  • Short talk on embeddings for the Massive Open Online Course: Computational Learning Theory and Beyond, organized by Karen Seidel

Publications

2024

Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs.
SIAM Journal on Discrete Mathematics 2024
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller
Real-World Networks Are Low-Dimensional: Theoretical and Practical Assessment.
International Joint Conference on Artificial Intelligence (IJCAI) 2024

2023

Maximilian Katzmann
About the analysis of algorithms on networks with underlying hyperbolic geometry (Über die Analyse von Algorithmen auf Netzwerken mit zugrundeliegender hyperbolischer Geometrie)
University of Potsdam, Germany 2023
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry.
Algorithmica 2023
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Maximilian Katzmann
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Theory of Computing Systems 2023
Davin Jeong, Allison Gunby-Mann, Sarel Cohen, Maximilian Katzmann, Chau Pham, Arnav Bhakta, Tobias Friedrich, Peter Chin
Deep Distance Sensitivity Oracles.
International Workshop on Complex Networks & Their Applications (COMPLEX NETWORKS) 2023
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, Ziena Zeif
On the Giant Component of Geometric Inhomogeneous Random Graphs.
European Symposium on Algorithms (ESA) 2023
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs.
International Colloquium on Automata, Languages and Programming (ICALP) 2023
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Daniel Stephan
Strongly Hyperbolic Unit Disk Graphs.
Symposium on Theoretical Aspects of Computer Science (STACS) 2023
Thomas Bläsius, Maximilian Katzmann, Marcus Wilhelm
Partitioning the Bags of a Tree Decomposition into Cliques.
Symposium on Experimental and Efficient Algorithms (SEA) 2023
Vanja Doskoc, Tobias Friedrich, Niko Hastrich, Maximilian Katzmann
Code for: Faster Nearest Neighbors Queries on Geographic Data.
2023
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller
Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs.
Computing Research Repository (CoRR) 2023
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Leon Schiller
A simple statistic for determining the dimensionality of complex networks.
Computing Research Repository (CoRR) 2023
Thomas Bläsius, Maximilian Katzmann, Marcus Wilhelm
Partitioning the Bags of a Tree Decomposition Into Cliques.
Computing Research Repository (CoRR) 2023
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, Ziena Zeif
On the Giant Component of Geometric Inhomogeneous Random Graphs.
Computing Research Repository (CoRR) 2023
Thomas Bläsius, Maximilian Katzmann, Clara Stegehuis
Maximal Cliques in Scale-Free Random Graphs.
Computing Research Repository (CoRR) 2023

2022

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, Christopher Weyand
Efficiently generating geometric inhomogeneous and hyperbolic random graphs.
Network Science 2022
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.
ACM Transactions on Algorithms (TALG) 2022
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Martin S. Krejca, Marcus Pappik
Algorithms for Hard-Constraint Point Processes via Discretization.
International Computing and Combinatorics Conference (COCOON) 2022
Sebastian Angrick, Ben Bals, Niko Hastrich, Maximilian Kleissl, Jonas Schmidt, Vanja Doskoc, Louise Molitor, Tobias Friedrich, Maximilian Katzmann
Towards explainable real estate valuation via evolutionary algorithms.
Annual Conference on Genetic and Evolutionary Computation (GECCO) 2022
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Martin S. Krejca, Marcus Pappik
Using random graphs to sample repulsive Gibbs point processes with arbitrary-range potentials.
Computing Research Repository (CoRR) 2022
Davin Jeong, Chau Pham, Arnav Bhakta, Sarel Cohen, Maximilian Katzmann, Tobias Friedrich, Sang (Peter) Chin
Deep Distance Sensitivity Oracles.
Computing Research Repository (CoRR) 2022

2021

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry.
European Symposium on Algorithms (ESA) 2021
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane.
Symposium on Experimental and Efficient Algorithms (SEA) 2021
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Daniel Stephan
Routing in Strongly Hyperbolic Unit Disk Graphs.
Computing Research Repository (CoRR) 2021
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, Martin S. Krejca, Marcus Pappik
Algorithms for general hard-constraint point processes via discretization.
Computing Research Repository (CoRR) 2021
Sebastian Angrick, Ben Bals, Niko Hastrich, Maximilian Kleissl, Jonas Schmidt, Vanja Doskoc, Maximilian Katzmann, Louise Molitor, Tobias Friedrich
Towards Explainable Real Estate Valuation via Evolutionary Algorithms.
Computing Research Repository (CoRR) 2021
Tobias Friedrich, Maximilian Katzmann, Leon Schiller
Computing Voronoi Diagrams in the Polar-Coordinate Model of the Hyperbolic Plane.
Computing Research Repository (CoRR) 2021

2020

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer
Hyperbolic Embeddings for Near-Optimal Greedy Routing.
ACM Journal of Experimental Algorithmics (JEA) 2020
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Maximilian Katzmann
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Symposium on Theoretical Aspects of Computer Science (STACS) 2020
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry.
Computing Research Repository (CoRR) 2020

2019

Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, Christopher Weyand
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
European Symposium on Algorithms (ESA) 2019
Álvaro Parra Bustos, Tat-Jun Chin, Frank Neumann, Tobias Friedrich, Maximilian Katzmann
A Practical Maximum Clique Algorithm for Matching with Pairwise Constraints.
Computing Research Repository (CoRR) 2019
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, Maximilian Katzmann
Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs.
Computing Research Repository (CoRR) 2019
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, Christopher Weyand
Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs.
Computing Research Repository (CoRR) 2019

2018

Tobias Friedrich, Maximilian Katzmann, Anton Krohmer
Unbounded Discrepancy of Deterministic Random Walks on Grids.
SIAM Journal on Discrete Mathematics 2018
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer
Hyperbolic Embeddings for Near-Optimal Greedy Routing.
Workshop on Algorithm Engineering and Experimentation (ALENEX) 2018
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.
International Colloquium on Automata, Languages and Programming (ICALP) 2018
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Anton Krohmer, Jonathan Striebel
Towards a Systematic Evaluation of Generative Network Models.
Workshop on Algorithms and Models for the Web-Graph (WAW) 2018
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry
Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry.
Computing Research Repository (CoRR) 2018

2017

Maximilian Katzmann, Christian Komusiewicz
Systematic Exploration of Larger Local Search Neighborhoods for the Minimum Vertex Cover Problem.
AAAI Conference on Artificial Intelligence (AAAI) 2017

2015

Tobias Friedrich, Maximilian Katzmann, Anton Krohmer
Unbounded Discrepancy of Deterministic Random Walks on Grids.
International Symposium on Algorithms and Computation (ISAAC) 2015