1 citations · 1 across the 7 of their papers we have counts for
8 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…
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…
Clustering with Few Disks to Minimize the Sum of Radii
Mikkel Abrahamsen, Sarita de Berg, Lucas Meijer +2
Given a set of points in the Euclidean plane, the -MinSumRadius problem asks to cover this point set using disks with the objective of minimizing the sum of the radii of…
3-Coloring in Time O(1.3217^n)
Lucas Meijer
We propose a new algorithm for 3-coloring that runs in time O(1.3217^n). For this algorithm, we make use of the time O(1.3289^n) algorithm for 3-coloring by Beigel and Eppstein. Th…
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…