11 citations · 119 across the 41 of their papers we have counts for
6 papers · 1 filter
Dynamic Toolbox for ETRINV
Mikkel Abrahamsen, Tillmann Miltzow
Recently, various natural algorithmic problems have been shown to be -complete. The reduction relied in many cases on the -completeness of t…
Smoothing the gap between NP and ER
Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
We study algorithmic problems that belong to the complexity class of the existential theory of the reals (ER). A problem is ER-complete if it is as hard as the problem ETR and if i…
A Universality Theorem for Nested Polytopes
Michael G. Dobbins, Andreas Holmsen, Tillmann Miltzow
In a nutshell, we show that polynomials and nested polytopes are topological, algebraic and algorithmically equivalent. Given two polytops and a number , the Nest…
Smoothed Analysis of Order Types
Ivor van der Hoog, Tillmann Miltzow, Martijn van Schaik
Consider an ordered point set , its order type (denoted by ) is a map which assigns to every triple of points a value in based on whether the…
On the VC-dimension of half-spaces with respect to convex sets
Nicolas Grelier, Saeed Gh. Ilchi, Tillmann Miltzow +1
A family S of convex sets in the plane defines a hypergraph H = (S, E) as follows. Every subfamily S' of S defines a hyperedge of H if and only if there exists a halfspace h that f…
Token Swapping on Trees
Ahmad Biniaz, Kshitij Jain, Anna Lubiw +6
The input to the token swapping problem is a graph with vertices , and tokens with labels , one on each vertex. The goal is to get token…