Till Miltzow

Till Miltzow is an Assistant Professor in the Department of Algorithms and Complexity at the Faculty of Science, Utrecht University. His research primarily focuses on computational geometry, algorithms, and complexity theory, with particular expertise in the existential theory of the reals (ER) and its applications to geometric problems.

Dr. Miltzow has established himself as a leading researcher in computational geometry, particularly known for his work on the Art Gallery Problem, where he and his collaborators proved the problem is ER-complete. His research spans a wide range of topics including geometric embeddings, Hausdorff distance computations, token swapping problems, and the complexity of various geometric decision problems.

His research interests include:

• Computational Geometry and Algorithm Design
• Complexity Theory, particularly the Existential Theory of the Reals (ER)
• Geometric Embeddings and Representations
• Art Gallery Problems and Polygon Guarding
• Computational Topology and Shape Analysis
• Algorithmic Game Theory

Dr. Miltzow's publications demonstrate a consistent focus on establishing the computational complexity of geometric problems, often showing ER-completeness for problems previously thought to be NP-hard. His work bridges theoretical computer science with practical geometric applications, contributing significantly to our understanding of the boundaries between tractable and intractable problems in computational geometry.

Among his notable achievements is the proof that the classic Art Gallery Problem is ER-complete, which resolved a long-standing open question about the problem's complexity. His research has been published in top-tier venues including the Journal of the ACM, SIAM Journal on Computing, and proceedings of major conferences like FOCS and SoCG.

Dr. Miltzow maintains an active research program with numerous collaborations across Europe and has made significant contributions to understanding the complexity landscape of geometric problems. His work has implications for computer graphics, robotics, and computer vision, where geometric decision problems frequently arise.