11 citations · 119 across the 41 of their papers we have counts for
52 papers
The Nesting Bird Box Problem is ER-complete: Sharp Hardness Results for the Hidden Set Problem
Lucas Meijer, Till Miltzow, Johanna Ockenfels +1
In the (Nesting) Bird Box Problem we are given a polygonal domain P and a number k and we want to know if there is a set B of k points inside P such that no two points in B can see…
Beyond Bits: An Introduction to Computation over the Reals
Tillmann Miltzow
We introduce a lightweight and accessible approach to computation over the real numbers, with the aim of clarifying both the underlying concepts and their relevance in modern resea…
Devil's Games and : Continuous Games complete for the First-Order Theory of the Reals
Lucas Meijer, Arnaud de Mesmay, Tillmann Miltzow +2
We introduce the complexity class Quantified Reals (). Let FOTR be the set of true sentences in the first-order theory of the reals. A language is in $\text…
On Equivalent Characterizations of the Polynomial Hierarchy in Abstract Models of Computation
Jeremy C. Kirn, Lucas Meijer, Tillmann Miltzow +1
We investigate machine models similar to Turing machines that are augmented with the operations of a first-order structure , and we show that under weak conditions on…
Oracle Separations for RPH
Thekla Hamm, Lucas Meijer, Tillmann Miltzow +1
While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real…
The Existential Theory of the Reals as a Complexity Class: A Compendium
Marcus Schaefer, Jean Cardinal, Tillmann Miltzow
We survey the complexity class , which captures the complexity of deciding the existential theory of the reals. The class has roots in two…
Recognition of Unit Segment and Polyline Graphs is -Complete
Michael Hoffmann, Tillmann Miltzow, Simon Weber +1
Given a set of objects in the plane, the corresponding intersection graph is defined as follows. Each object defines a vertex and an edge joins two vertices whenever the corres…
Geometric Thickness of Multigraphs is -complete
Henry Förster, Philipp Kindermann, Tillmann Miltzow +3
We say that a (multi)graph has geometric thickness if there exists a straight-line drawing and a -coloring of its edges where no…
Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
Sarita de Berg, Tillmann Miltzow, Frank Staals
We devise a data structure that can answer shortest path queries for two query points in a polygonal domain on vertices. For any , the space complexity of…
The Complexity of Recognizing Geometric Hypergraphs
Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist +2
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hyp…
Representing Matroids over the Reals is -complete
Eun Jung Kim, Arnaud de Mesmay, Tillmann Miltzow
A matroid is an ordered pair , where is a finite set called the ground set and a collection called the independent sets which satisfy the conditions…
Sometimes Two Irrational Guards are Needed
Lucas Meijer, Tillmann Miltzow
In the art gallery problem, we are given a closed polygon , with rational coordinates and an integer . We are asked whether it is possible to find a set (of guards) of si…
Avoider-Enforcer Game is NP-hard
Tillmann Miltzow, Miloš Stojaković
In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enforcer alternate in claiming an unclaimed vertex, until all the vertices of the hypergraph are claimed. Enforc…
Training Fully Connected Neural Networks is -Complete
Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut +2
We consider the problem of finding weights and biases for a two-layer fully connected neural network to fit a given set of data points as well as possible, also known as EmpiricalR…
The Complexity of the Hausdorff Distance
Paul Jungeblut, Linda Kleist, Tillmann Miltzow
We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algeb…
Topological Art in Simple Galleries
Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow +2
Let be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in . We say two points can see each…
Geometric Embeddability of Complexes is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
We show that the decision problem of determining whether a given (abstract simplicial) -complex has a geometric embedding in is complete for the Existential Theory…
On Classifying Continuous Constraint Satisfaction Problems
Tillmann Miltzow, Reinier F. Schmiermann
A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain . We engage in a systematic study to cl…
Chasing Puppies: Mobile Beacon Routing on Closed Curves
Mikkel Abrahamsen, Jeff Erickson, Irina Kostitsyna +5
We solve an open problem posed by Michael Biro at CCCG 2013 that was inspired by his and others' work on beacon-based routing. Consider a human and a puppy on a simple closed curve…
Training Neural Networks is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
Given a neural network, training data, and a threshold, it was known that it is NP-hard to find weights for the neural network such that the total error is below the threshold. We…
Local Complexity of Polygons
Fabian Klute, Meghana M. Reddy, Tillmann Miltzow
Many problems in Discrete and Computational Geometry deal with simple polygons or polygonal regions. Many algorithms and data-structures perform considerably faster, if the underly…
Between Shapes, Using the Hausdorff Distance
Marc van Kreveld, Tillmann Miltzow, Tim Ophelders +2
Given two shapes and in the plane with Hausdorff distance , is there a shape with Hausdorff distance to and from and ? The answer is always yes, and dep…
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Simon Hengeveld, Tillmann Miltzow
Given a closed simple polygon , we say two points see each other if the segment is fully contained in . The art gallery problem seeks a minimum size set $G\subset…
Framework for -Completeness of Two-Dimensional Packing Problems
Mikkel Abrahamsen, Tillmann Miltzow, Nadja Seiferth
The aim in packing problems is to decide if a given set of pieces can be placed inside a given container. A packing problem is defined by the types of pieces and containers to be h…