Tillmann Miltzow

According to our database, Tillmann Miltzow authored at least 68 papers between 2010 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

Geometric Thickness of Multigraphs is $\exists \mathbb {R}$-Complete.

Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, Birgit Vogtenhuber

Algorithmica, February, 2026

2025

On Equivalent Characterizations of NP in Abstract Models of Computation.

Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow, Hans L. Bodlaender

CoRR, October, 2025

Oracle Separations for RPH.

Thekla Hamm, Lucas Meijer, Tillmann Miltzow, Subhasree Patro

CoRR, February, 2025

2024

Framework for ∃ ℝ-Completeness of Two-Dimensional Packing Problems.

Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth

TheoretiCS, 2024

Representing Matroids over the Reals is ∃ℝ-complete.

Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow

Discret. Math. Theor. Comput. Sci., 2024

The Existential Theory of the Reals as a Complexity Class: A Compendium.

Marcus Schaefer, Jean Cardinal, Tillmann Miltzow

CoRR, 2024

Recognition of Unit Segment and Polyline Graphs is ∃R-Complete.

Michael Hoffmann, Tillmann Miltzow, Simon Weber, Lasse Wulf

CoRR, 2024

Recognition of Unit Segment and Polyline Graphs is $\exists \mathbb {R} $-Complete.

Michael Hoffmann, Tillmann Miltzow, Simon Weber, Lasse Wulf

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2024

Geometric Thickness of Multigraphs is ∃ ℝ-Complete.

Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, Birgit Vogtenhuber

Proceedings of the LATIN 2024: Theoretical Informatics, 2024

Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain.

Sarita de Berg, Tillmann Miltzow, Frank Staals

Proceedings of the 40th International Symposium on Computational Geometry, 2024

2023

Completeness for the Complexity Class $\forall \exists \mathbb {R}$ and Area-Universality.

Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski

Discret. Comput. Geom., July, 2023

Training Fully Connected Neural Networks is ∃R-Complete.

Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, Simon Weber

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

The Complexity of Recognizing Geometric Hypergraphs.

Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist, Tillmann Miltzow, Simon Weber

Proceedings of the Graph Drawing and Network Visualization - 31st International Symposium, 2023

Geometric Embeddability of Complexes Is ∃ℝ-Complete.

Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Proceedings of the 39th International Symposium on Computational Geometry, 2023

2022

Token Swapping on Trees.

Ahmad Biniaz, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, Alexi Turcotte

Discret. Math. Theor. Comput. Sci., 2022

Sometimes Two Irrational Guards are Needed.

Lucas Meijer, Tillmann Miltzow

CoRR, 2022

Avoider-Enforcer Game is NP-hard.

Tillmann Miltzow, Milos Stojakovic

CoRR, 2022

Topological Art in Simple Galleries.

Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, Simon Weber

Proceedings of the 5th Symposium on Simplicity in Algorithms, 2022

The Complexity of the Hausdorff Distance.

Paul Jungeblut, Linda Kleist, Tillmann Miltzow

Proceedings of the 38th International Symposium on Computational Geometry, 2022

2021

On the VC-dimension of half-spaces with respect to convex sets.

Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky

Discret. Math. Theor. Comput. Sci., 2021

Local Complexity of Polygons.

Fabian Klute, Meghana M. Reddy, Tillmann Miltzow

CoRR, 2021

Training Neural Networks is ER-complete.

Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

On Classifying Continuous Constraint Satisfaction problems.

Tillmann Miltzow, Reinier F. Schmiermann

Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science, 2021

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem.

Simon B. Hengeveld, Tillmann Miltzow

Proceedings of the 37th International Symposium on Computational Geometry, 2021

Chasing Puppies: Mobile Beacon Routing on Closed Curves.

Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi L. Vermeulen, Giovanni Viglietta

Proceedings of the 37th International Symposium on Computational Geometry, 2021

2020

Halving balls by a hyperplane in deterministic linear time.

Michael Hoffmann, Vincent Kusters, Tillmann Miltzow

J. Comput. Geom., 2020

Between Shapes, Using the Hausdorff Distance.

Marc J. van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, Jordi L. Vermeulen

Proceedings of the 31st International Symposium on Algorithms and Computation, 2020

Maximum Clique in Disk-Like Intersection Graphs.

Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

Framework for ER-Completeness of Two-Dimensional Packing Problems.

Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Smoothing the gap between NP and ER.

Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition).

Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, Jules Wulms

Proceedings of the 36th International Symposium on Computational Geometry, 2020

2019

Dynamic Toolbox for ETRINV.

Mikkel Abrahamsen, Tillmann Miltzow

CoRR, 2019

A Framework for Robust Realistic Geometric Computations.

Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow

CoRR, 2019

A Universality Theorem for Nested Polytopes.

Michael Gene Dobbins, Andreas F. Holmsen, Tillmann Miltzow

CoRR, 2019

Smoothed Analysis of Order Types.

Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik

CoRR, 2019

On the VC-dimension of convex sets and half-spaces.

Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky

CoRR, 2019

Parameterized Streaming Algorithms for Min-Ones d-SAT.

Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2019

2018

Smoothed Analysis of the Art Gallery Problem.

Michael Gene Dobbins, Andreas F. Holmsen, Tillmann Miltzow

CoRR, 2018

∀∃ℝ-Completeness and Area-Universality.

Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

The art gallery problem is ∃ ℝ-complete.

Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

The Complexity of Drawing a Graph in a Polygonal Region.

Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal

Proceedings of the Graph Drawing and Network Visualization - 26th International Symposium, 2018

2017

Intersection Graphs of Rays and Grounded Segments.

Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, Birgit Vogtenhuber

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2017

Obedient Plane Drawings for Disk Intersection Graphs.

Bahareh Banyassady, Michael Hoffmann, Boris Klemz, Maarten Löffler, Tillmann Miltzow

Proceedings of the Algorithms and Data Structures - 15th International Symposium, 2017

Complexity of Token Swapping and its Variants.

Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

An Approximation Algorithm for the Art Gallery Problem.

Édouard Bonnet, Tillmann Miltzow

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Fine-Grained Complexity of Coloring Unit Disks and Balls.

Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

Irrational Guards are Sometimes Needed.

Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow

Proceedings of the 33rd International Symposium on Computational Geometry, 2017

2016

Tight Exact and Approximate Algorithmic Results on Token Swapping.

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno

CoRR, 2016

The Parameterized Hardness of the Art Gallery Problem.

Édouard Bonnet, Tillmann Miltzow

CoRR, 2016

Flip Distance to a Non-crossing Perfect Matching.

Édouard Bonnet, Tillmann Miltzow

CoRR, 2016

Approximation and Hardness of Token Swapping.

Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Parameterized Hardness of Art Gallery Problems.

Édouard Bonnet, Tillmann Miltzow

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems.

Dániel Marx, Tillmann Miltzow

Proceedings of the 32nd International Symposium on Computational Geometry, 2016

2015

Quasi-parallel segments and characterization of unique bichromatic matchings.

Andrei Asinowski, Tillmann Miltzow, Günter Rote

J. Comput. Geom., 2015

Counting K₄-subdivisions.

Tillmann Miltzow, Jens M. Schmidt, Mingji Xia

Discret. Math., 2015

Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position.

Oswin Aichholzer, Andrei Asinowski, Tillmann Miltzow

Electron. J. Comb., 2015

Upper and Lower Bounds on Long Dual Paths in Line Arrangements.

Udo Hoffmann, Linda Kleist, Tillmann Miltzow

Proceedings of the Mathematical Foundations of Computer Science 2015, 2015

2014

Counting K_4-Subdivisions.

Tillmann Miltzow, Jens M. Schmidt, Mingji Xia

CoRR, 2014

Counting One-sided Exchange Stable Matchings.

Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow

CoRR, 2014

Reprint of: Extreme point and halving edge search in abstract order types.

Oswin Aichholzer, Tillmann Miltzow, Alexander Pilz

Comput. Geom., 2014

Counting Houses of Pareto Optimal Matchings in the House Allocation Problem.

Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow

Proceedings of the Fun with Algorithms - 7th International Conference, 2014

Halving Balls in Deterministic Linear Time.

Michael Hoffmann, Vincent Kusters, Tillmann Miltzow

Proceedings of the Algorithms - ESA 2014, 2014

2013

Extreme point and halving edge search in abstract order types.

Oswin Aichholzer, Tillmann Miltzow, Alexander Pilz

Comput. Geom., 2013

2012

Trees in simple Polygons

Tillmann Miltzow

CoRR, 2012

Augmenting a Geometric Matching is NP-complete

Tillmann Miltzow

CoRR, 2012

Tron, a Combinatorial Game on Abstract Graphs.

Tillmann Miltzow

Proceedings of the Fun with Algorithms - 6th International Conference, 2012

2011

Points with Large Quadrant Depth.

Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow, Rom Pinchasi, Torsten Ueckerdt, Ran Ziv

J. Comput. Geom., 2011

2010

Points with large quadrant-depth.

Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Rom Pinchasi, Tillmann Miltzow

Proceedings of the 26th ACM Symposium on Computational Geometry, 2010