6 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…
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…
First-Order Logic and Twin-Width for Some Geometric Graphs
Colin Geniet, Gunwoo Kim, Lucas Meijer
For some geometric graph classes, tractability of testing first-order formulas is precisely characterised by the graph parameter twin-width. This was first proved for interval grap…
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…