11 citations · 119 across the 41 of their papers we have counts for
16 papers · 1 filter
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…
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…
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…
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…
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…
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…
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…
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…
The Complexity of Drawing a Graph in a Polygonal Region
Anna Lubiw, Tillmann Miltzow, Debajyoti Mondal
We prove that the following problem is complete for the existential theory of the reals: Given a planar graph and a polygonal region, with some vertices of the graph assigned to po…
Complexity of Token Swapping and its Variants
Édouard Bonnet, Tillmann Miltzow, Paweł Rzążewski
In the Token Swapping problem we are given a graph with a token placed on each vertex. Each token has exactly one destination vertex, and we try to move all the tokens to their des…
Approximation and Hardness for Token Swapping
Tillmann Miltzow, Lothar Narins, Yoshio Okamoto +3
Given a graph with , we place on every vertex a token . A swap is an exchange of tokens on adjacent vertices. We consider the algorithmi…
Augmenting a Geometric Matching is -complete
Tillmann Miltzow
Given points in the plane, it is well-known that there always exists a perfect straight-line non-crossing matching. We show that it is -complete to decide if a partial mat…
Tron, a combinatorial Game on abstract Graphs
Tillmann Miltzow
We study the combinatorial two-player game Tron. We answer the extremal question on general graphs and also consider smaller graph classes. Bodlaender and Kloks conjectured in [2]…