Publications
2023
Scholarly publications
Kim, E., Mesmay, A. D., & Miltzow, T. (2023). Representing Matroids over the Reals is existsR-complete. (pp. 1-22). arXiv. https://doi.org/10.48550/arXiv.2301.03221
2022
Scholarly publications
Meijer, L., & Miltzow, T. (2022). Sometimes Two Irrational Guards are Needed. (pp. 1-19). arXiv. https://doi.org/10.48550/arXiv.2212.01211
Miltzow, T., & Stojakovic, M. (2022). Avoider-Enforcer Game is NP-hard. (pp. 1-8). arXiv. https://doi.org/10.48550/arXiv.2208.06687
Bertschinger, D., Hertrich, C., Jungeblut, P., Miltzow, T., & Weber, S. (2022). Training Fully Connected Neural Networks is existsR-Complete. (pp. 1-40). arXiv. https://doi.org/10.48550/arXiv.2204.01368
Jungeblut, P., Kleist, L., & Miltzow, T. (2022). The Complexity of the Hausdorff Distance. In X. Goaoc, & M. Kerber (Eds.), 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany (Vol. 224, pp. 48:1-48:17). [48] (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 224). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2022.48
Lubiw, A., Miltzow, T., & Mondal, D. (2022). The Complexity of Drawing a Graph in a Polygonal Region. Journal of Graph Algorithms and Applications, 26(4), 421-446. [4]. https://doi.org/10.7155/jgaa.00602
Abrahamsen, M., Adamaszek, A., & Miltzow, T. (2022). The Art Gallery Problem is ER-complete. Journal of the ACM, 69(1), 4:1-4:70. [4]. https://doi.org/10.1145/3486220
Kreveld, M. V., Miltzow, T., Ophelders, T., Sonke, W., & Vermeulen, J. L. (2022). Between shapes, using the Hausdorff distance. Computational geometry, 100, 1-14. [101817]. https://doi.org/10.1016/j.comgeo.2021.101817
2021
Scholarly publications
Klute, F., Reddy, M. M., & Miltzow, T. (2021). Local Complexity of Polygons. (pp. 1-7). arXiv. https://doi.org/10.48550/arXiv.2101.07554
Abrahamsen, M., Kleist, L., & Miltzow, T. (2021). Training Neural Networks is ER-complete. (pp. 1-12). arXiv. https://doi.org/10.48550/arXiv.2102.09798
Bertschinger, D., El Maalouly, N., Miltzow, T., Schnider, P., & Weber, S. (2021). Topological Art in Simple Galleries. (pp. 1-39). arXiv. https://doi.org/10.48550/arXiv.2108.04007
Abrahamsen, M., Kleist, L., & Miltzow, T. (2021). Geometric Embeddability of Complexes is ∃R-complete. (pp. 1-27). arXiv. https://doi.org/10.48550/arXiv.2108.02585
Miltzow, T., & Schmiermann, R. (2021). On Classifying Continuous Constraint Satisfaction Problems. (pp. 1-40). arXiv. https://doi.org/10.48550/arXiv.2106.02397
Hengeveld, S., & Miltzow, T. (2021). A Practical Algorithm with Performance Guarantees for the Art Gallery Problem.. 1-16. Paper presented at 37th International Symposium on Computational Geometry . https://doi.org/10.4230/LIPIcs.SoCG.2021.44
Miltzow, T., Abrahamsen, M., Erickson, J., Kostitsyna, I., Urhausen, J., Vermeulen, J., & Viglietta, G. (2021). Chasing Puppies: Mobile Beacon Routing on Closed Curves. 5:1-5:19. Paper presented at 37th International Symposium on Computational Geometry . https://doi.org/10.4230/LIPIcs.SoCG.2021.5
2020
Scholarly publications
Hoffmann, M., Kusters, V., & Miltzow, T. (2020). Halving balls by a hyperplane in deterministic linear time. Journal of Computational Geometry, 11(1), 576-614. https://doi.org/10.20382/jocg.v11i1a23
Abrahamsen, M., Miltzow, T., & Seiferth, N. (2020). Framework for ER-Completeness of Two-Dimensional Packing Problems. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020 (pp. 1014-1021). IEEE. https://doi.org/10.1109/FOCS46700.2020.00098
Hengeveld, S., & Miltzow, T. (Accepted/In press). A Practical Algorithm with Performance Guarantees for the ArttextasciitildeGallery Problem. CoRR, abs/2007.06920.
van Kreveld, M. J., Miltzow, T., Ophelders, T., Sonke, W., & Vermeulen, J. L. (2020). Between Shapes, Using the Hausdorff Distance. In Y. Cao, S-W. Cheng, & M. Li (Eds.), 31st International Symposium on Algorithms and Computation (ISAAC 2020) (pp. 13:1-13:16). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 181). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.ISAAC.2020.13
Bonnet, É., Miltzow, T., & Grelier, N. (2020). Maximum Clique in Disk-Like Intersection Graphs. In N. Saxena, & S. Simon (Eds.), 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) (pp. 17:1-17:18). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 182). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.FSTTCS.2020.17
Miltzow, T., Parada, I., Sonke, W., Speckmann, B., & Wulms, J. (2020). Hiding Sliding Cubes: Why Reconfiguring Modular Robots Is Not Easy (Media Exposition). In S. Cabello, & D. Z. Chen (Eds.), 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland (Vol. 164, pp. 1-5). [78] (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2020.78
Bonnet, É., & Miltzow, T. (2020). Parameterized Hardness of Art Gallery Problems. ACM transactions on algorithms, 16(4), 1-23. [42]. https://doi.org/10.1145/3398684
Abrahamsen, M., Miltzow, T., & Seiferth, N. (2020). Framework for existsR-Completeness of Two-Dimensional Packing Problems. (pp. 1-69). arXiv. https://doi.org/10.48550/arXiv.2004.07558
2019
Scholarly publications
Abrahamsen, M., & Miltzow, T. (2019). Dynamic Toolbox for ETRINV. arXiv. https://doi.org/10.48550/arXiv.1912.08674
Hoog, I. V. D., Miltzow, T., & Schaik, M. V. (2019). Smoothed Analysis of Order Types. arXiv.org.
https://dspace.library.uu.nl/bitstream/handle/1874/390405/smoothed.pdf?sequence=1
https://dspace.library.uu.nl/bitstream/handle/1874/390405/smoothed.pdf?sequence=1
Erickson, J., Hoog, I. V. D., & Miltzow, T. (2019). A Framework for Robust Realistic Geometric Computations. arXiv.org, [02278].
https://dspace.library.uu.nl/bitstream/handle/1874/390404/1912.02278.pdf?sequence=1
https://dspace.library.uu.nl/bitstream/handle/1874/390404/1912.02278.pdf?sequence=1
Dobbins, M. G., Holmsen, A., & Miltzow, T. (2019). A Universality Theorem for Nested Polytopes. arXiv.org.
https://dspace.library.uu.nl/bitstream/handle/1874/389402/A_Universality_Theorem_for_Nested_Polytopes.pdf?sequence=1
https://dspace.library.uu.nl/bitstream/handle/1874/389402/A_Universality_Theorem_for_Nested_Polytopes.pdf?sequence=1
Grelier, N., Ilchi, S. G., Miltzow, T., & Smorodinsky, S. (2019). On the VC-dimension of convex sets and half-spaces. arXiv.org.
https://dspace.library.uu.nl/bitstream/handle/1874/390403/1907.01241.pdf?sequence=1
https://dspace.library.uu.nl/bitstream/handle/1874/390403/1907.01241.pdf?sequence=1
Biniaz, A., Jain, K., Lubiw, A., Masárová, Z., Miltzow, T., Mondal, D., Naredla, A. M., Tkadlec, J., & Turcotte, A. (2019). Token Swapping on Trees. arXiv.org.
Agrawal, A., Biswas, Bonnet, Brettell, Curticapean, Marx, Miltzow, T., Raman, & Saurabh (2019). Parameterized streaming algorithms for Min-Ones d-SAT. In A. Chattopadhyay, & P. Gastin (Eds.), 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) (LIPIcs - Leibniz International Proceedings in Informatics; Vol. 150). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH.
2018
Scholarly publications
Dobbins, M. G., Holmsen, A. F., & Miltzow, T. (2018). Smoothed Analysis of the Art Gallery Problem. CoRR, abs/1811.01177. http://arxiv.org/abs/1811.01177
Dobbins, M. G., Kleist, L., Miltzow, T., & Rzazewski, P. (2018). forallexistsR-Completeness and Area-Universality. In A. Brandstädt, E. Köhler, & K. Meer (Eds.), Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings (Vol. 11159, pp. 164-175). (Lecture Notes in Computer Science). Springer Verlag. https://doi.org/10.1007/978-3-030-00256-514
Abrahamsen, M., Adamaszek, A., & Miltzow, T. (2018). The art gallery problem is exists R-complete. In I. Diakonikolas, D. Kempe, & M. Henzinger (Eds.), Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018, Los Angeles, CA, USA, June 25-29, 2018 (pp. 65-73). ACM. https://doi.org/10.1145/3188745.3188868
Biró, C., Bonnet, É., Marx, D., Miltzow, T., & Rzazewski, P. (2018). Fine-grained complexity of coloring unit disks and balls. Journal of Computational Geometry, 9(2), 47-80. https://doi.org/10.20382/jocg.v9i2a4
Cardinal, J., Felsner, S., Miltzow, T., Tompkins, C., & Vogtenhuber, B. (2018). Intersection Graphs of Rays and Grounded Segments. Journal of Graph Algorithms and Applications, 22(2), 273-295. https://doi.org/10.7155/jgaa.00470
Bonnet, É., Miltzow, T., & Rzazewski, P. (2018). Complexity of Token Swapping and Its Variants. Algorithmica, 80(9), 2656-2682. https://doi.org/10.1007/s00453-017-0387-0
2017
Scholarly publications
Bonnet, É., & Miltzow, T. (2017). An Approximation Algorithm for the Art Gallery Problem. In B. Aronov, & M. J. Katz (Eds.), 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia (Vol. 77, pp. 20:1-20:15). (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2017.20
Abrahamsen, M., Adamaszek, A., & Miltzow, T. (2017). Irrational Guards are Sometimes Needed. In B. Aronov, & M. J. Katz (Eds.), 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia (Vol. 77, pp. 3:1-3:15). (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2017.3
2016
Scholarly publications
Bonnet, É., & Miltzow, T. (2016). The Parameterized Hardness of the Art Gallery Problem. CoRR, abs/1603.08116. http://arxiv.org/abs/1603.08116
Miltzow, T., Narins, L., Okamoto, Y., Rote, G., Thomas, A., & Uno, T. (2016). Tight Exact and Approximate Algorithmic Results on Token Swapping. CoRR, abs/1602.05150. http://arxiv.org/abs/1602.05150
Bonnet, É., & Miltzow, T. (2016). Flip Distance to a Non-crossing Perfect Matching. CoRR, abs/1601.05989. http://arxiv.org/abs/1601.05989
Miltzow, T., Narins, L., Okamoto, Y., Rote, G., Thomas, A., & Uno, T. (2016). Approximation and Hardness of Token Swapping. In P. Sankowski, & C. D. Zaroliagis (Eds.), 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark (Vol. 57, pp. 66:1-66:15). (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.ESA.2016.66
Marx, D., & Miltzow, T. (2016). Peeling and Nibbling the Cactus: Subexponential-Time Algorithms for Counting Triangulations and Related Problems. In S. P. Fekete, & A. Lubiw (Eds.), 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA (Vol. 51, pp. 52:1-52:16). (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik GmbH. https://doi.org/10.4230/LIPIcs.SoCG.2016.52
Asinowski, A., Keszegh, B., & Miltzow, T. (2016). Counting houses of Pareto optimal matchings in the house allocation problem. Discrete Mathematics, 339(12), 2919-2932. https://doi.org/10.1016/j.disc.2016.05.027
2015
Scholarly publications
Hoffmann, U., Kleist, L., & Miltzow, T. (2015). Upper and Lower Bounds on Long Dual-Paths in Line Arrangements. CoRR, abs/1506.03728. http://arxiv.org/abs/1506.03728
Hoffmann, U., Kleist, L., & Miltzow, T. (2015). Upper and Lower Bounds on Long Dual Paths in Line Arrangements. In G. F. Italiano, G. Pighizzini, & D. Sannella (Eds.), Mathematical Foundations of Computer Science 2015 - 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II (Vol. 9235, pp. 407-419). (Lecture Notes in Computer Science). Springer Verlag. https://doi.org/10.1007/978-3-662-48054-034
Asinowski, A., Miltzow, T., & Rote, G. (2015). Quasi-parallel segments and characterization of unique bichromatic matchings. Journal of Computational Geometry, 6(1), 185-219. https://doi.org/10.20382/jocg.v6i1a8
Miltzow, T., Schmidt, J. M., & Xia, M. (2015). Counting K_4-subdivisions. Discrete Mathematics, 338(12), 2387-2392. https://doi.org/10.1016/j.disc.2015.06.004
Aichholzer, O., Asinowski, A., & Miltzow, T. (2015). Disjoint Compatibility Graph of Non-Crossing Matchings of Points in Convex Position. Electronic Journal of Combinatorics, 22(1), 1. https://doi.org/10.37236/4403
2014
Scholarly publications
Miltzow, T., Schmidt, J. M., & Xia, M. (2014). Counting K4-Subdivisions. CoRR, abs/1411.4819. http://arxiv.org/abs/1411.4819
Asinowski, A., Keszegh, B., & Miltzow, T. (2014). Counting One-sided Exchange Stable Matchings. CoRR, abs/1401.5354. http://arxiv.org/abs/1401.5354
Hoffmann, M., Kusters, V., & Miltzow, T. (2014). Halving Balls in Deterministic Linear Time. In A. S. Schulz, & D. Wagner (Eds.), Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings (Vol. 8737, pp. 566-578). (Lecture Notes in Computer Science). Springer Verlag. https://doi.org/10.1007/978-3-662-44777-247
Aichholzer, O., Miltzow, T., & Pilz, A. (2014). Reprint of: Extreme point and halving edge search in abstract order types. Computational Geometry: Theory and Applications, 47(3), 518-526. https://doi.org/10.1016/j.comgeo.2013.11.002
2013
Scholarly publications
Aichholzer, O., Miltzow, T., & Pilz, A. (2013). Extreme point and halving edge search in abstract order types. Computational Geometry: Theory and Applications, 46(8), 970-978. https://doi.org/10.1016/j.comgeo.2013.05.001
2012
Scholarly publications
Miltzow, T. (2012). Augmenting a Geometric Matching is NP-complete. CoRR, abs/1206.6360. http://arxiv.org/abs/1206.6360
Miltzow, T. (2012). Tron, a Combinatorial Game on Abstract Graphs. In E. Kranakis, D. Krizanc, & F. L. Luccio (Eds.), Fun with Algorithms - 6th International Conference, FUN 2012, Venice, Italy, June 4-6, 2012. Proceedings (Vol. 7288, pp. 293-304). (Lecture Notes in Computer Science). Springer Verlag. https://doi.org/10.1007/978-3-642-30347-029
2011
Scholarly publications
Apfelbaum, R., Ben-Dan, I., Felsner, S., Miltzow, T., Pinchasi, R., Ueckerdt, T., & Ziv, R. (2011). Points with Large Quadrant Depth. Journal of Computational Geometry, 2(1), 128-143. https://doi.org/10.20382/jocg.v2i1a7