Prof. Dr. Linda Kleist

Short Biography

Linda is professor for theoretical computer science, especially algorithms and complexity, at the University Hamburg since August 2025. Before that, she was a professor for theoretical computer sciencee at University Potsdam since August 2024, a PostDoc at the Technical University Braunschweig, a guest researcher at the University of Kopenhagen and Utrecht University, and an academic staff member at the Technical University Berlin. Her research interest include algorithms and complexity for graphs and geometry,  computational geometry, and geometric optimization.

Research Interest

... lie in a wide range of 

• algorithms and complexity
• graphs and geometry
• geometric optimization problems

• packing
• covering
• reconfiguration
• geometric representations of graphs
• online algorithms
• approximation algorithms
• existential theory of the reals

Publications

Some selected publications.

• Geometric Embeddability of Complexes is ∃R-complete
  with Mikkel Abrahamsen and Tillmann Miltzow
  Journal of the ACM, 2025
  in Proceedings of 39th Symposium on Computational Geometry (SoCG 2023)
  arXiv: 2108.02585
• A solution to Ringel's problem
  with James Davies, Chaya Keller, Shakhar Smorodinsky, and Bartosz Walczak
  Journal of the European Mathematical Society (JEMS), 2024
  in Proceedings of 38th Symposium on Computational Geometry (SoCG 2022)
  arXiv: 2112.05042
  media attention: [video], [Gil Kalai's blog], [NRC article], [Haaretz article]
• Flipping Non-Crossing Spanning Trees
  with Håvard Bjerkevik, Torsten Ueckerdt, and Birgit Vogtenhuber
  Symposium on Discrete Algorithms (SODA 2025)
  arXiv: 2410.23809
• Facet-Hamiltonicity
  with Hugo Akitaya, Jean Cardinal, Stefan Felsner, Robert Lauff
  Symposium on Discrete Algorithms (SODA 2025)
  arXiv: 2411.02172
• Online Sorting and Translational Packing of Convex Polygons
  with Anders Aamand, Mikkel Abrahamsen and Lorenzo Beretta
  in Proceedings of Symposium on Discrete Algorithms (SODA 2023)
  arXiv: 22112.03791

For lists of my works, consult dblp, orcid, or google scholar.

Teaching

Winter Semester 2025/2026

• Algorithms and Datastructures
• Bachelor Seminar: 
• Oberseminar

In the upcoming semester, we plan a course on computational geometry. 

If you are interested in bachelor or master thesis supervision, please reach out by email.