Tillmann Miltzow

We devise a data structure that can answer shortest path queries for two query points in a polygonal domain \( P \) on \( n \) vertices. For any \(\varepsilon > 0\) , the space complexity of the data structure is \(O(n^{10+\varepsilon})\) and queries can be answered in \(O(\log n)\) time. Alternatively, we can achieve a space complexity of \(O(n^{9+\varepsilon})\) by relaxing the query time to \(O(\log^{2}n)\) . This is the first improvement upon a conference paper by Chiang and Mitchell [ 15 ] from 1999. They present a data structure with \(O(n^{11})\) space complexity and \(O(\log n)\) query time. Our main result can be extended to include a space-time tradeoff. Specifically, we devise data structures with \(O(n^{9+\varepsilon}/\ell^{4+O(\varepsilon)})\) space complexity and \(O(\ell\log^{2}n)\) query time, for any integer \(1\leq\ell\leq n\) . Furthermore, we present improved data structures for the special case where we restrict one (or both) of the query points to lie on the boundary of \( P \) . When one of the query points is restricted to lie on the boundary, and the other query point is unrestricted, the space complexity becomes \(O(n^{6+\varepsilon})\) and the query time \(O(\log^{2}n)\) . When both query points are on the boundary, the space complexity is decreased further to \(O(n^{4+\varepsilon})\) and the query time to \(O(\log n)\) , thereby improving an earlier result of Bae and Okamoto.

We say that a (multi)graph $$ \user2{G} = (\user2{V},\user2{E}) $$ has geometric thickness t if there exists a straight-line drawing $$ \user2{\varphi }:\user2{V} \to \mathbb{R}^{{\mathbf{2}}} $$ and a t -coloring of its edges where no two edges sharing a point in their relative interior have the same color. The Geometric Thickness problem asks whether a given multigraph has geometric thickness at most t . This problem was shown to be NP-hard for $$ \user2{t} = \mathbf{2} $$ (Durocher et al. Comput Geom 56:1–18, 2016. https://doi.org/10.1016/j.comgeo.2016.03.003 ). In this paper, we settle the computational complexity of Geometric Thickness by showing that it is $$\exists \mathbb {R}$$ -complete already for thickness 30 . Moreover, our reduction shows that the problem is $$\exists \mathbb {R}$$ -complete for 4392 -planar graphs, where a graph is k -planar if it admits a topological drawing with at most k crossings per edge. In the course of our paper we answer previous questions on geometric thickness and on other related problems, in particular that simultaneous graph embeddings of 31 edge-disjoint graphs and pseudo-segment stretchability with chromatic number 30 are $$\exists \mathbb {R}$$ -complete.

We survey the complexity class $\exists \mathbb{R}$, which captures the complexity of deciding the existential theory of the reals. The class $\exists \mathbb{R}$ has roots in two different traditions, one based on the Blum-Shub-Smale model of real computation, and the other following work by Mnëv and Shor on the universality of realization spaces of oriented matroids. Over the years the number of problems for which $\exists \mathbb{R}$ rather than NP has turned out to be the proper way of measuring their complexity has grown, particularly in the fields of computational geometry, graph drawing, game theory, and some areas in logic and algebra. $\exists \mathbb{R}$ has also started appearing in the context of machine learning, Markov decision processes, and probabilistic reasoning. We have aimed at collecting a comprehensive compendium of problems complete and hard for $\exists \mathbb{R}$, as well as a long list of open problems. The compendium is presented in the third part of our survey; a tour through the compendium and the areas it touches on makes up the second part. The first part introduces the reader to the existential theory of the reals as a complexity class, discussing its history, motivation and prospects as well as some technical aspects.

A continuous constraint satisfaction problem (CCSP) is a constraint satisfaction problem (CSP) with an interval domain $U \subset \mathbb{R}$. We engage in a systematic study to classify CCSPs that are complete of the Existential Theory of the Reals, i.e., ER-complete. To define this class, we first consider the problem ETR, which also stands for Existential Theory of the Reals. In an instance of this problem we are given some sentence of the form $\exists x_1, \ldots, x_n \in \mathbb{R} : \Phi(x_1, \ldots, x_n)$, where $\Phi$ is a well-formed quantifier-free formula consisting of the symbols $\{0, 1, +, \cdot, \geq, >, \wedge, \vee, \neg\}$, the goal is to check whether this sentence is true. Now the class ER is the family of all problems that admit a polynomial-time many-one reduction to ETR. It is known that NP $\subseteq$ ER $\subseteq$ PSPACE. We restrict our attention on CCSPs with addition constraints ($x + y = z$) and some other mild technical conditions. Previously, it was shown that multiplication constraints ($x \cdot y = z$), squaring constraints ($x^2 = y$), or inversion constraints ($x\cdot y = 1$) are sufficient to establish ER-completeness. We extend this in the strongest possible sense for equality constraints as follows. We show that CCSPs (with addition constraints and some other mild technical conditions) that have any one well-behaved curved equality constraint ($f(x,y) = 0$) are ER-complete. We further extend our results to inequality constraints. We show that any well-behaved convexly curved and any well-behaved concavely curved inequality constraint ($f(x,y) \geq 0$ and $g(x,y) \geq 0$) imply ER-completeness on the class of such CCSPs.

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 EmpiricalRiskMinimization. Our main result is that the associated decision problem is $\exists\mathbb{R}$-complete, that is, polynomial-time equivalent to determining whether a multivariate polynomial with integer coefficients has any real roots. Furthermore, we prove that algebraic numbers of arbitrarily large degree are required as weights to be able to train some instances to optimality, even if all data points are rational. Our result already applies to fully connected instances with two inputs, two outputs, and one hidden layer of ReLU neurons. Thereby, we strengthen a result by Abrahamsen, Kleist and Miltzow [NeurIPS 2021]. A consequence of this is that a combinatorial search algorithm like the one by Arora, Basu, Mianjy and Mukherjee [ICLR 2018] is impossible for networks with more than one output dimension, unless $\mathsf{NP}=\exists\mathbb{R}$.

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-algebraic sets is bounded by a given threshold is complete for the complexity class $${ \forall \exists _{<}\mathbb {R}} $$∀ ∃ < R . This implies that the problem is -, -, $$\exists \mathbb {R} $$∃ R -, and $$\forall \mathbb {R} $$∀ R -hard.

Let P be a simple polygon, then the art gallery problem is looking for a minimum set of points (guards) that can see every point in P. We say two points $$a,b\in P$$a , b ∈ P can see each other if the line segment $${\text {seg}} (a,b)$$seg ( a , b ) is contained in P. We denote by V(P) the family of all minimum guard placements. The Hausdorff distance makes V(P) a metric space and thus a topological space. We show homotopy-universality, that is, for every semi-algebraic set S there is a polygon P such that V(P) is homotopy equivalent to S. Furthermore, for various concrete topological spaces T, we describe instances I of the art gallery problem such that V(I) is homeomorphic to T.