Tillmann Miltzow

113 papers A* 16A 5B 5Misc 2Journal 78Unranked 7

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Beyond Bits: An Introduction to Computation over the Reals. CoRR Tillmann Miltzow
2026	J	`jnl`	Geometric Thickness of Multigraphs is $\exists \mathbb {R}$-Complete. Algorithmica Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, Birgit Vogtenhuber
2025	J	`jnl`	Devil's Games and Qℝ: Continuous Games complete for the First-Order Theory of the Reals. CoRR Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow, Marcus Schaefer, Jack Stade
2025	J	`jnl`	Geometric Embeddability of Complexes is ∃ℝ-complete. J. ACM Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
2025	J	`jnl`	On Equivalent Characterizations of NP in Abstract Models of Computation. CoRR Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow, Hans L. Bodlaender
2025	J	`jnl`	Oracle Separations for RPH. CoRR Thekla Hamm, Lucas Meijer, Tillmann Miltzow, Subhasree Patro
2024	J	`jnl`	Framework for ∃ ℝ-Completeness of Two-Dimensional Packing Problems. TheoretiCS Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
2024	—	`conf`	Geometric Thickness of Multigraphs is ∃ ℝ-Complete. LATIN (1) Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, Birgit Vogtenhuber
2024	J	`jnl`	On Classifying Continuous Constraint Satisfaction Problems. TheoretiCS Tillmann Miltzow, Reinier F. Schmiermann
2024	B	`conf`	Recognition of Unit Segment and Polyline Graphs is $\exists \mathbb {R} $-Complete. WG Michael Hoffmann, Tillmann Miltzow, Simon Weber, Lasse Wulf
2024	J	`jnl`	Recognition of Unit Segment and Polyline Graphs is ∃R-Complete. CoRR Michael Hoffmann, Tillmann Miltzow, Simon Weber, Lasse Wulf
2024	J	`jnl`	Representing Matroids over the Reals is ∃ℝ-complete. Discret. Math. Theor. Comput. Sci. Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow
2024	J	`jnl`	Smoothing the Gap Between NP and ER. SIAM J. Comput. Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
2024	J	`jnl`	The Complexity of the Hausdorff Distance. Discret. Comput. Geom. Paul Jungeblut, Linda Kleist, Tillmann Miltzow
2024	J	`jnl`	The Existential Theory of the Reals as a Complexity Class: A Compendium. CoRR Marcus Schaefer, Jean Cardinal, Tillmann Miltzow
2024	J	`jnl`	Topological Art in Simple Galleries. Discret. Comput. Geom. Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, Simon Weber
2024	A*	`conf`	Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain. SoCG Sarita de Berg, Tillmann Miltzow, Frank Staals
2023	J	`jnl`	A Practical Algorithm with Performance Guarantees for the Art Gallery Problem. Discret. Math. Theor. Comput. Sci. Simon B. Hengeveld, Tillmann Miltzow
2023	J	`jnl`	Completeness for the Complexity Class $\forall \exists \mathbb {R}$ and Area-Universality. Discret. Comput. Geom. Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski
2023	A*	`conf`	Geometric Embeddability of Complexes Is ∃ℝ-Complete. SoCG Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
2023	J	`jnl`	Geometric Thickness of Multigraphs is ∃R-complete. CoRR Henry Förster, Philipp Kindermann, Tillmann Miltzow, Irene Parada, Soeren Terziadis, Birgit Vogtenhuber
2023	J	`jnl`	Representing Matroids over the Reals is ∃R-complete. CoRR Eunjung Kim, Arnaud de Mesmay, Tillmann Miltzow
2023	—	`conf`	The Complexity of Recognizing Geometric Hypergraphs. GD (1) Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist, Tillmann Miltzow, Simon Weber
2023	J	`jnl`	The Complexity of Recognizing Geometric Hypergraphs. CoRR Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist, Tillmann Miltzow, Simon Weber
2023	J	`jnl`	Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain. CoRR Sarita de Berg, Tillmann Miltzow, Frank Staals
2023	A*	`conf`	Training Fully Connected Neural Networks is ∃R-Complete. NeurIPS Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, Simon Weber
2022	J	`jnl`	Avoider-Enforcer Game is NP-hard. CoRR Tillmann Miltzow, Milos Stojakovic
2022	J	`jnl`	Between shapes, using the Hausdorff distance. Comput. Geom. Marc J. van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, Jordi L. Vermeulen
2022	J	`jnl`	Sometimes Two Irrational Guards are Needed. CoRR Lucas Meijer, Tillmann Miltzow
2022	J	`jnl`	The Art Gallery Problem is ∃ℝ-complete. J. ACM Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
2022	J	`jnl`	The Complexity of Drawing a Graph in a Polygonal Region. J. Graph Algorithms Appl. Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal
2022	A*	`conf`	The Complexity of the Hausdorff Distance. SoCG Paul Jungeblut, Linda Kleist, Tillmann Miltzow
2022	J	`jnl`	Token Swapping on Trees. Discret. Math. Theor. Comput. Sci. Ahmad Biniaz, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, Alexi Turcotte
2022	—	`conf`	Topological Art in Simple Galleries. SOSA Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, Simon Weber
2022	J	`jnl`	Training Fully Connected Neural Networks is ∃R-Complete. CoRR Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, Simon Weber
2021	A*	`conf`	A Practical Algorithm with Performance Guarantees for the Art Gallery Problem. SoCG Simon B. Hengeveld, Tillmann Miltzow
2021	A*	`conf`	Chasing Puppies: Mobile Beacon Routing on Closed Curves. SoCG Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi L. Vermeulen, Giovanni Viglietta
2021	J	`jnl`	Chasing Puppies: Mobile Beacon Routing on Closed Curves. CoRR Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna, Maarten Löffler, Tillmann Miltzow, Jérôme Urhausen, Jordi L. Vermeulen, Giovanni Viglietta
2021	J	`jnl`	Geometric Embeddability of Complexes is ∃R-complete. CoRR Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
2021	J	`jnl`	Local Complexity of Polygons. CoRR Fabian Klute, Meghana M. Reddy, Tillmann Miltzow
2021	A*	`conf`	On Classifying Continuous Constraint Satisfaction problems. FOCS Tillmann Miltzow, Reinier F. Schmiermann
2021	J	`jnl`	On Classifying Continuous Constraint Satisfaction problems. CoRR Tillmann Miltzow, Reinier F. Schmiermann
2021	J	`jnl`	On the VC-dimension of half-spaces with respect to convex sets. Discret. Math. Theor. Comput. Sci. Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky
2021	J	`jnl`	The Complexity of the Hausdorff Distance. CoRR Paul Jungeblut, Linda Kleist, Tillmann Miltzow
2021	J	`jnl`	Topological Art in Simple Galleries. CoRR Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, Simon Weber
2021	A*	`conf`	Training Neural Networks is ER-complete. NeurIPS Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
2021	J	`jnl`	Training Neural Networks is ER-complete. CoRR Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
2020	J	`jnl`	A Practical Algorithm with Performance Guarantees for the Art~Gallery Problem. CoRR Simon B. Hengeveld, Tillmann Miltzow
2020	B	`conf`	Between Shapes, Using the Hausdorff Distance. ISAAC Marc J. van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, Jordi L. Vermeulen
2020	J	`jnl`	Between Shapes, Using the Hausdorff Distance. CoRR Marc J. van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, Jordi L. Vermeulen
2020	A*	`conf`	Framework for ER-Completeness of Two-Dimensional Packing Problems. FOCS Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
2020	J	`jnl`	Framework for ∃R-Completeness of Two-Dimensional Packing Problems. CoRR Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
2020	J	`jnl`	Halving balls by a hyperplane in deterministic linear time. J. Comput. Geom. Michael Hoffmann, Vincent Kusters, Tillmann Miltzow
2020	A*	`conf`	Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition). SoCG Tillmann Miltzow, Irene Parada, Willem Sonke, Bettina Speckmann, Jules Wulms
2020	—	`conf`	Maximum Clique in Disk-Like Intersection Graphs. FSTTCS Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
2020	J	`jnl`	Maximum Clique in Disk-Like Intersection Graphs. CoRR Édouard Bonnet, Nicolas Grelier, Tillmann Miltzow
2020	J	`jnl`	Parameterized Hardness of Art Gallery Problems. ACM Trans. Algorithms Édouard Bonnet, Tillmann Miltzow
2020	A*	`conf`	Smoothing the gap between NP and ER. FOCS Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
2019	J	`jnl`	A Framework for Robust Realistic Geometric Computations. CoRR Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
2019	J	`jnl`	A Universality Theorem for Nested Polytopes. CoRR Michael Gene Dobbins, Andreas F. Holmsen, Tillmann Miltzow
2019	J	`jnl`	Dynamic Toolbox for ETRINV. CoRR Mikkel Abrahamsen, Tillmann Miltzow
2019	J	`jnl`	On the VC-dimension of convex sets and half-spaces. CoRR Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow, Shakhar Smorodinsky
2019	—	`conf`	Parameterized Streaming Algorithms for Min-Ones d-SAT. FSTTCS Akanksha Agrawal, Arindam Biswas, Édouard Bonnet, Nick Brettell, Radu Curticapean, Dániel Marx, Tillmann Miltzow, Venkatesh Raman, Saket Saurabh
2019	J	`jnl`	Smoothed Analysis of Order Types. CoRR Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik
2019	J	`jnl`	Token Swapping on Trees. CoRR Ahmad Biniaz, Kshitij Jain, Anna Lubiw, Zuzana Masárová, Tillmann Miltzow, Debajyoti Mondal, Anurag Murty Naredla, Josef Tkadlec, Alexi Turcotte
2018	J	`jnl`	Complexity of Token Swapping and Its Variants. Algorithmica Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski
2018	J	`jnl`	Fine-grained complexity of coloring unit disks and balls. J. Comput. Geom. Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski
2018	J	`jnl`	Intersection Graphs of Rays and Grounded Segments. J. Graph Algorithms Appl. Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, Birgit Vogtenhuber
2018	J	`jnl`	Smoothed Analysis of the Art Gallery Problem. CoRR Michael Gene Dobbins, Andreas F. Holmsen, Tillmann Miltzow
2018	A	`conf`	The Complexity of Drawing a Graph in a Polygonal Region. GD Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal
2018	J	`jnl`	The Complexity of Drawing a Graph in a Polygonal Region. CoRR Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal
2018	A*	`conf`	The art gallery problem is ∃ ℝ-complete. STOC Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
2018	B	`conf`	∀∃ℝ-Completeness and Area-Universality. WG Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski
2017	A*	`conf`	An Approximation Algorithm for the Art Gallery Problem. SoCG Édouard Bonnet, Tillmann Miltzow
2017	A	`conf`	Complexity of Token Swapping and its Variants. STACS Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski
2017	A*	`conf`	Fine-Grained Complexity of Coloring Unit Disks and Balls. SoCG Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, Pawel Rzazewski
2017	B	`conf`	Intersection Graphs of Rays and Grounded Segments. WG Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, Birgit Vogtenhuber
2017	A*	`conf`	Irrational Guards are Sometimes Needed. SoCG Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
2017	J	`jnl`	Irrational Guards are Sometimes Needed. CoRR Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
2017	B	`conf`	Obedient Plane Drawings for Disk Intersection Graphs. WADS Bahareh Banyassady, Michael Hoffmann, Boris Klemz, Maarten Löffler, Tillmann Miltzow
2017	J	`jnl`	The Art Gallery Problem is ∃ℝ-complete. CoRR Mikkel Abrahamsen, Anna Adamaszek, Tillmann Miltzow
2017	J	`jnl`	∀∃R-completeness and area-universality. CoRR Michael Gene Dobbins, Linda Kleist, Tillmann Miltzow, Pawel Rzazewski
2016	J	`jnl`	An Approximation Algorithm for the Art Gallery Problem. CoRR Édouard Bonnet, Tillmann Miltzow
2016	A	`conf`	Approximation and Hardness of Token Swapping. ESA Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno
2016	J	`jnl`	Complexity of Token Swapping and its Variants. CoRR Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski
2016	J	`jnl`	Counting houses of Pareto optimal matchings in the house allocation problem. Discret. Math. Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow
2016	J	`jnl`	Flip Distance to a Non-crossing Perfect Matching. CoRR Édouard Bonnet, Tillmann Miltzow
2016	J	`jnl`	Intersection Graphs of Rays and Grounded Segments. CoRR Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, Birgit Vogtenhuber
2016	A	`conf`	Parameterized Hardness of Art Gallery Problems. ESA Édouard Bonnet, Tillmann Miltzow
2016	A*	`conf`	Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. SoCG Dániel Marx, Tillmann Miltzow
2016	J	`jnl`	Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. CoRR Dániel Marx, Tillmann Miltzow
2016	J	`jnl`	The Parameterized Hardness of the Art Gallery Problem. CoRR Édouard Bonnet, Tillmann Miltzow
2016	J	`jnl`	Tight Exact and Approximate Algorithmic Results on Token Swapping. CoRR Tillmann Miltzow, Lothar Narins, Yoshio Okamoto, Günter Rote, Antonis Thomas, Takeaki Uno
2015	J	`jnl`	Counting K Discret. Math. Tillmann Miltzow, Jens M. Schmidt, Mingji Xia
2015	J	`jnl`	Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position. Electron. J. Comb. Oswin Aichholzer, Andrei Asinowski, Tillmann Miltzow
2015	J	`jnl`	Quasi-parallel segments and characterization of unique bichromatic matchings. J. Comput. Geom. Andrei Asinowski, Tillmann Miltzow, Günter Rote
2015	—	`conf`	Upper and Lower Bounds on Long Dual Paths in Line Arrangements. MFCS (2) Udo Hoffmann, Linda Kleist, Tillmann Miltzow
2015	J	`jnl`	Upper and Lower Bounds on Long Dual-Paths in Line Arrangements. CoRR Udo Hoffmann, Linda Kleist, Tillmann Miltzow
2014	Misc	`conf`	Counting Houses of Pareto Optimal Matchings in the House Allocation Problem. FUN Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow
2014	J	`jnl`	Counting K_4-Subdivisions. CoRR Tillmann Miltzow, Jens M. Schmidt, Mingji Xia
2014	J	`jnl`	Counting One-sided Exchange Stable Matchings. CoRR Andrei Asinowski, Balázs Keszegh, Tillmann Miltzow
2014	J	`jnl`	Disjoint compatibility graph of non-crossing matchings of points in convex position. CoRR Oswin Aichholzer, Andrei Asinowski, Tillmann Miltzow
2014	A	`conf`	Halving Balls in Deterministic Linear Time. ESA Michael Hoffmann, Vincent Kusters, Tillmann Miltzow
2014	J	`jnl`	Halving Balls in Deterministic Linear Time. CoRR Michael Hoffmann, Vincent Kusters, Tillmann Miltzow
2014	J	`jnl`	Reprint of: Extreme point and halving edge search in abstract order types. Comput. Geom. Oswin Aichholzer, Tillmann Miltzow, Alexander Pilz
2013	J	`jnl`	Extreme point and halving edge search in abstract order types. Comput. Geom. Oswin Aichholzer, Tillmann Miltzow, Alexander Pilz
2013	J	`jnl`	Quasi-Parallel Segments and Characterization of Unique Bichromatic Matchings CoRR Andrei Asinowski, Tillmann Miltzow, Günter Rote
2012	J	`jnl`	Augmenting a Geometric Matching is NP-complete CoRR Tillmann Miltzow
2012	J	`jnl`	Trees in simple Polygons CoRR Tillmann Miltzow
2012	Misc	`conf`	Tron, a Combinatorial Game on Abstract Graphs. FUN Tillmann Miltzow
2011	J	`jnl`	Points with Large Quadrant Depth. J. Comput. Geom. Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Tillmann Miltzow, Rom Pinchasi, Torsten Ueckerdt, Ran Ziv
2011	J	`jnl`	Tron, a combinatorial Game on abstract Graphs CoRR Tillmann Miltzow
2010	—	`conf`	Points with large quadrant-depth. SCG Roel Apfelbaum, Itay Ben-Dan, Stefan Felsner, Rom Pinchasi, Tillmann Miltzow