# Representing Matroids over the Reals is $\exists\mathbb{R}$-complete

Eunjung Kim, Arnaud de Mesmay, Tillmann Miltzow

###### Abstract

A _matroid_ $M$ is an ordered pair $(E,\mathcal{I})$, where $E$ is a finite
set called the _ground set_ and a collection $\mathcal{I}\subset 2^{E}$ called
the _independent sets_ which satisfy the conditions: (I1)
$\emptyset\in\mathcal{I}$, (I2) $I^{\prime}\subset I\in\mathcal{I}$ implies
$I^{\prime}\in\mathcal{I}$, and (I3) $I_{1},I_{2}\in\mathcal{I}$ and
$|I_{1}|<|I_{2}|$ implies that there is an $e\in I_{2}$ such that
$I_{1}\cup\\{e\\}\in\mathcal{I}$. The _rank_ ${\sf rk}(M)$ of a matroid $M$ is
the maximum size of an independent set. We say that a matroid
$M=(E,\mathcal{I})$ is representable over the reals if there is a map
$\varphi:E\rightarrow\mathbb{R}^{{\sf rk}(M)}$ such that $I\in\mathcal{I}$ if
and only if $\varphi(I)$ forms a linearly independent set.

We study the problem of Matroid $\mathbb{R}$-Representability over the reals.
Given a matroid $M$, we ask whether there is a set of points in the Euclidean
space representing $M$. We show that Matroid $\mathbb{R}$-Representability is
$\exists\mathbb{R}$-complete, already for matroids of rank $3$. The complexity
class $\exists\mathbb{R}$ can be defined as the family of algorithmic problems
that is polynomial-time equivalent to determining if a multivariate polynomial
with integer coefficients has a real root.

Our methods are similar to previous methods from the literature. Yet, the
result itself was never pointed out and there is no proof readily available in
the language of computer science.

##  1 Introduction

Many articles on matroids assume that the matroid is representable [40, 15,
17]. Representability either heavily simplifies proofs and definitions or is
even essential. We show that the question of representability over the reals
is as difficult as the existential theory of the reals, that is
$\exists\mathbb{R}$-complete. The complexity class $\exists\mathbb{R}$ can be
defined as the family of algorithmic problems that is polynomial-time
equivalent to determining if a multivariate polynomial (with integer
coefficients) has a real root, see below for an introduction and overview of
this complexity class.

#### Definitions.

Before we give a general definition of a matroid, we introduce _vector
matroids_. Given a matrix $A$ over a field $\mathbb{F}$, we can define the
corresponding vector matroid $M[A]=(E,\mathcal{I})$ as follows. The ground set
$E$ of $M[A]$ is formed by the columns of $A$ and we say that a subset
$I\subset E$ is independent in $M$, i.e., $I\in\mathcal{I}$, if the columns
are linearly independent over $\mathbb{F}$. A set of elements of $E$ which is
not independent is said to be dependent. Note that any set of columns
containing a zero column is dependent. The independent sets of a vector
matroid satisfy three simple properties (see below). One way to look at
matroids is to see them as abstract set systems that have those three
properties. A _matroid_ $M$ is an ordered pair $(E,\mathcal{I})$, where $E$ is
a finite set called the _ground set_ and a collection $\mathcal{I}\subset
2^{E}$ called the _independent sets_ which satisfy the conditions:

  * (I1)

$\emptyset\in\mathcal{I}$,

  * (I2)

$I^{\prime}\subset I\in\mathcal{I}$ implies $I^{\prime}\in\mathcal{I}$,

  * (I3)

$I_{1},I_{2}\in\mathcal{I}$ and $|I_{1}|<|I_{2}|$ implies that there is an
$e\in I_{2}$ such that $I_{1}\cup\\{e\\}\in\mathcal{I}$.

The _rank_ ${\sf rk}(M)$ of a matroid $M$ is the maximum size of an
independent set. We say that a matroid $M=(E,\mathcal{I})$ is representable
over $\mathbb{F}$ if there is a matrix $A$ over $\mathbb{F}$ such that
$M=M[A]$. Note that all columns of $A$ live in a subspace of dimension at most
${\sf rk}(M[A])$. Therefore, we can assume without loss of generality that the
columns of $A$ have dimension ${\sf rk}(M[A])$. We refer to [50] for more
background on matroids.

Given a matroid $M$, if there exists a matrix $A$ over $\mathbb{R}$ such that
$M=M[A]$, we say that $M$ is representable over the reals. The algorithmic
problem of Matroid $\mathbb{R}$-Representability is to test whether a given
matroid is representable over the reals. Since we only discuss the real case
in this article, we will sometimes say representable as a shorthand. Note that
we also need to specify how the matroid $M$ is given. In the literature on
matroids, one has often an oracle such that one can ask the oracle for each
set $I$ whether $I\in\mathcal{I}$. We will deviate from this practice, as it
might be unclear how to describe the oracle. Instead, we will just list all
sets in $\mathcal{I}$ explicitly. This does not blow up the description
complexity too much in our case, as we will deal mainly with constant rank
matroids.

#### Geometric Interpretation.

If we have a representation $A\in\mathbb{R}^{3\times n}$ of a matroid
$M=M[A]$, we can scale every column of $A$ by a nonzero number and it stays a
valid representation. This is also the case if we scale by $-1$. Furthermore,
if we rotate $A$ (i.e., multiply it on the left with an orthogonal
transformation) it still stays a valid representation. Thus, in case we have a
representable rank-$3$ matroid over $\mathbb{R}$, we can assume that there is
a representation in which all nonzero vectors have their third coordinate
equal to $1$. In this way, we can consider the columns of $A$ as a point
configuration in the plane with $z=1$. The property of three vectors being
dependent translates to the corresponding three points to lie on a common
line.

In this geometric interpretation, we could have considered any plane different
from the one with $z=1$, as long as it does not cross the origin. This would
have yielded a different point configuration. The resulting transformation is
called a _projective transformation_. It maps lines to lines, except for one
line that disappears, we say that it is _sent to infinity_. Conversely, for
any line in the plane, there exists a projective transformation that sends it
to infinity. Throughout this article, we think of representations of rank-$3$
matroids via these point configurations, and thus we will slightly abuse
language by calling such a point configuration a representation.

#### A motivating example.

One of the standard examples to illustrate realizability is the so-called Fano
plane. It is the matroid on seven elements whose maximal independent sets are
all the triples except

$\\{1,4,7\\},\\{1,2,3\\},\\{1,5,6\\},\\{3,6,7\\},\\{2,5,7\\},\\{3,4,5\\},\\{2,4,6\\}.$

This can be represented pictorially as in the figure below, where the lines
and the circle denote the dependencies.

An immediate question that arises from this picture is whether a picture
exists where the circle is not used and the dependencies are all pictured by
lines. This is equivalent to asking whether the Fano matroid is representable
over the reals. It is well-known not to be [50, Proposition 6.4.8]. The
problem Matroid $\mathbb{R}$-Representability addresses the general question
of deciding which matroids can be represented like that, and our main result
is that this problem is $\exists\mathbb{R}$-complete.

#### Order Types.

We saw above that matroids are an abstraction to describe point collinearities
in the plane. I.e., if we have a rank 3 matroid then every dependent set
corresponds to three collinear points. Now given a set of points, we are often
also interested in the orientation of each triple: either clockwise, counter-
clockwise, or collinear.

In this example, $\\{a,b,c\\}$ is collinear and $(a,b,d)$, $(a,c,d)$, and
$(b,c,d)$ are oriented counter-clockwise. This leads to the definition of
(abstract) order types, which is a pair $O=(E,\chi)$. Again, $E$ is a finite
set called the ground set. And

$\chi:\binom{E}{3}\rightarrow\\{-1,0,1\\}$

is a function called a _chirotope_ satisfying a few simple properties that are
derived from the intuition given above. We say that a point set
$P\subset\mathbb{R}^{2}$ represents a given order type $O=(E,\chi)$, if $P$
has for each element $e\in E$ a corresponding point $e^{\prime}\in P$.
Furthermore, for each triple $a,b,c\in E$ the corresponding points
$a^{\prime},b^{\prime},c^{\prime}\in P$ are oriented according to
$\chi(\\{a,b,c\\})$. Note that if we lift every point in $P$ to the plane with
$z=1$ as a subset of $\mathbb{R}^{3}$, then we get the following
correspondence between
$(p_{x}^{\prime},p_{y}^{\prime},1),(q_{x}^{\prime},q_{y}^{\prime},1),(r_{x}^{\prime},r_{y}^{\prime},1)$
and the corresponding elements $p,q,r\in E$.

$\text{sign}\,\det\left(\begin{matrix}p_{x}^{\prime}&q_{x}^{\prime}&r_{x}^{\prime}\\\
p_{y}^{\prime}&q_{y}^{\prime}&r_{y}^{\prime}\\\
1&1&1\end{matrix}\right)=\chi(p,q,r).$

Note that in this specific setup a realization of a rank 3 matroid and order
types are closely related. While matroids only determine the collinearities,
the order type also determines the orientation of each triple. We want to
point out that every abstract order type can be represented by a pseudoline
arrangement. A pseudoline arrangement can be defined as a collection of
$x$-monotone curves such that any pair of curves intersect exactly once. The
orientation of a triple of pseudolines is defined by the orientation of the
triangle that they form (a degenerate triangle corresponding to a zero
orientation).

Note that this pseudoline arrangement corresponds to the order type example
given above. Now, the realizability of the order types is equivalent to the
stretchability of pseudoline arrangements. That is finding a line arrangement
with the same combinatorics as the pseudoline arrangement. It is one of the
central theorems in the field of the existential theory of the reals that
stretchability is $\exists\mathbb{R}$-complete. We will use many ideas of that
proof for our main result.

We also want to point out that the notion of an order type can be easily
generalized to dimension $d$. The chirotope becomes a function of all $d+1$
tuples and tells us the orientation in $d$ dimensions. To illustrate this, if
we have four points $a,b,c,e$ in $3$-space, then the points $a,b,c$ lie one a
hyperplane $H$. Then the chirotope tells us on which side of $H$ the point $e$
lies, for an orientation of $H$ defined by the three points $a$,$b$ and $c$.

$\ell$
---
$a$
---
$b$
---
$c$
---
$d$
---
$e$
---
$f$
---
$f$
---
$a$
---
$b$
---
$c$
---
$d$
---
$e$
---
Figure 1: As $\ell$ separates $f$ from the other points, a projective
transformation sending the line $\ell$ at infinity will flip the orientation
of the triangles involving $f$ while keeping the other orientations unchanged.

It is important to note that if we take a projective transformation of the
plane, we preserve the represented matroid. This is because lines are mapped
to lines and points to points. However, projective transformations do not
preserve the order type of a point set. This is because a point may end up on
the other side of some line, as pictured in Figure 1. In order to get a closer
relationship, we work (sometimes) with matroids endowed with a distinguished
line at infinity $\ell_{\infty}$. Then we consider _valid_ representations of
such matroids, which are those where this line is at infinity (i.e., all the
points lie on one side of it). This definition extends to rank-$k$ matroids
using a hyperplane at infinity. This leads to the following definition.

Given an order type $O$, we say that a matroid $M$ _simulates_ $O$, if the
underlying matroid of $O$ is a subset of $M$ and if the following conditions
are met:

  * •

Any representation of the matroid underlying $O$ extends to a representation
of $M$.

  * •

Any valid representation of $M$ induces an point set representing $O$.

Note that when $M$ simulates $O$, then $M$ has a representation if and only if
$O$ has an oriented representation: indeed, starting with a representation of
$M$, one can always send the line at infinity to infinity using a projective
transformation and thus obtain a valid representation..

### Our results

Our main theorem is that Matroid $\mathbb{R}$-Representability is complete for
the existential theory of the reals.

######  Theorem 1.

Matroid $\mathbb{R}$-Representability is $\exists\mathbb{R}$-complete.

We provide two proofs of Theorem 1. The first one relies on simulating
arbitrary ETR-formulas using addition and multiplication and some technical
assumptions. There is a somewhat easier proof, starting from the fact that
order type realizability is $\exists\mathbb{R}$-complete, and then simulating
order types using normal matroids.

######  Theorem 2.

Let $k\geq 3$ be a fixed integer. Given a rank-$k$ order type $O$, we can
compute in linear time a rank-$k$ matroid $M$ such that $M$ simulates $O$.

Theorem 1 easily follows from Theorem 2 as deciding whether an order type is
representable over the reals is $\exists\mathbb{R}$-complete. This follows
from techniques dating back to the proof of the Mnëv Universality Theorem (see
[44, 52]). However, as explained in [44], the proof that stretchability is
$\exists\mathbb{R}$-hard requires a significant number of intricate steps,
some of which can be simplified in the setting of Matroid
$\mathbb{R}$-Representability. Indeed, the need for different scales (see for
example [44, Proof of Theorem 4.6]), which is the main difficulty in the
oriented case, can be completely circumvented in our case. Therefore, for the
sake of completeness and simplicity, we also provide a self-contained proof of
Theorem 1. We think it might be educational to first understand the proof of
Theorem 1, before one tries to understand the $\exists\mathbb{R}$-completeness
of stretchability.

#### Proof Overview.

In order to give an idea of the direct proof of Theorem 1, we first describe
an incorrect proof sketch. Then we point out the issues with this first sketch
and how we can fix them.

First, it is folklore that in order to prove $\exists\mathbb{R}$-completeness,
it is sufficient to find a way to encode variables and some basic operations
like addition ($x+y=z$) and multiplication ($xy=z$). We can force points to
lie on a specific line $\ell$ to represent our variables. Furthermore, using
the well-known von Staudt constructions we can simulate all the basic
constraints, see Figure 2 for the construction to simulate addition. This
(almost) describes a rank three matroid $M$. Furthermore, in any realization
of $M$, we can read a valid variable assignment.

$\mathbf{0}$
---
$\mathbf{x}$
---
$\mathbf{y}$
---
$\mathbf{x}+\mathbf{y}$
---
$\ell$
---
Figure 2: Encoding addition geometrically.

The issue with this basic approach is that it could be that there is only one
realization of $M$ such that two points coincide, or three points lie on a
common line, accidentally. If we were able to anticipate this, we could easily
specify this in the description of the matroid, but in general, this is not
easy.

We circumvent this general position issue with two fixes. The first fix is to
reduce from a version of ETR, where we can assume that all variable values are
distinct. We call this variant Distinct-ETR, see Section 2. The second fix is
to observe that when we build the von Staudt construction, we can ensure that
all helper points have enough freedom to avoid any coincidences or
collinearities with previously defined points, see Section 3. With these two
fixes, the above proof sketch works as is explained in Theorem 1.

The proof idea of Theorem 2 goes as follows. Using arithmetic operations, we
can give a variable the value $y=x^{2}\geq 0$. Geometrically, this implies
that the point representing $y$ is on the same side of the common line $\ell$
as the point representing $1$. In other words, we can enforce two points to
lie on the same side of a line with respect to a given point. We lift this to
half-spaces in the plane and higher dimensions. In this way, we can enforce
consistent orientations of the matroid with the given order type.

#### Results on Distinct-ETR.

We define the problem Distinct-ETR as a variant of ETR as follows (cf. infra
for a proper definition of ETR). We are given variables
$X=\\{x_{1},\ldots,x_{n}\\}$ and constraints of the form

$x+y=z,\quad x\cdot y=z,\quad x=1,\quad x>0,$

for $x,y,z\in X.$ Furthermore, we are promised that there is either no
solution at all or there is a solution $(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}$
such that $x_{i}\neq x_{j}$ for all $i\neq j$. We show the following theorem
in Section 2, which might be of independent interest.

######  Theorem 3.

Distinct-ETR is $\exists\mathbb{R}$-complete.

While we could not find any prior proof of Theorem 1 in the literature (hence
this work), there are many related works from at least two perspectives.
First, as already mentioned, when one considers order-types instead of
unoriented matroids, Theorem 1 is very well-known. Second, topological
universality theorems have been proved for the real-representability of
matroids in the algebraic geometry literature, see for example Lafforgue [38]
and Lee and Vakil [39]. While our work uses tools that are similar in spirit
to those papers, it differs in that our constructions are arguably simpler and
that we specifically focus on proving the computational hardness result, which
is not the point of focus of those previous works, and is not entirely
equivalent (see discussion below). Furthermore, we believe that it is
worthwhile to have a complete proof of Theorem 1 in a purely combinatorial
language, as opposed to the scheme-theoretical setup of previous works.

Shor’s proof of the Mnëv universality theorem [59, Section 4] introduces an
intermediate problem called the existential theory of totally real ordered
variables, which is very similar to Distinct-ETR but features totally ordered
variables $x_{1}<x_{2}\ldots<x_{n}$ as opposed to just requiring distinctness
in our problem. This ordering is desirable when one investigates oriented
matroids, and unneeded for unoriented ones. This difference allows for a proof
that is arguably simpler than his, or at least different.

### Background and Related Work

#### Matroids and Greedy

A practical reason why matroids are relevant for computational purposes is
that they capture in a simple way the class of discrete objects where greedy
algorithms are successful in finding an optimal solution. For example, the
standard Kruskal and Prim algorithms to compute a Minimum Spanning Tree in a
weighted graph can be abstracted by considering the vector matroid defined by
an oriented incidence matrix of the graph (called a _graphic matroid_), and
then generalized to compute in polynomial time a maximum or minimum-weight
basis for any matroid. This property actually characterizes matroids, see for
example Oxley [50, Section 1.8]

#### Some applications of representability.

For an algorithm on matroids, a suitable encoding scheme of the input matroid
is needed. A common way is to take the input matroid $M=(E,\mathcal{I})$ in
the form of an independence oracle which answers whether a given subset of the
ground elements $E$ is independent or not. There are algorithms which run with
polynomial number of oracle queries to such an oracle, for example a maximum
weight independent set of a given matroid can be computed in this way.
However, for many natural matroid properties, it is known that there is no
algorithm with polynomially bounded queries to independence oracle [29]
including the representability over $GF(2)$ and the connectivity of a matroid.

A vector representation of a matroid offers a compelling alternative to an
independence oracle as matroid operations can be substantially more efficient
using matrix operations. Matroid parity problem, a common generalization of
graph matching and matroid intersection problem, is solvable in polynomial
time given a vector representation [40] while super-polynomial number of calls
are needed under the independence oracle model [29]. Deciding whether the
branch-width of a matroid is at most $k$ is a common generalization of
computing the branch-width, rank-width and carving-width of a graph. While
there is an algorithm with $n^{O(k)}$ queries on an $n$ element matroid for
this problem [49] under the oracle model, whether the dependency on $k$ in the
exponent can be replaced by a uniform constant is not known till now. In
contrast, the branch-width of a vector matroid can be computed in $f(k)\cdot
n^{3}$ time [30] when the given representation is over a finite field
$\mathbb{F}$.

Another powerful application of a vector representation can be found in the
theory of kernelization in parameterized complexity. A surprising discovery of
[37] is that for many graph cut problems, compressing the input boils down to
finding a so-called representative set of a matroid. When the said matroid is
a vector matroid, a representative set of bounded size can be efficiently
computed in polynomial time [42, 43]. It turns out that solutions to graph cut
problems can be encoded as independent sets in gammoids, which form a well-
known class of representable matroids and of which a vector representation can
be constructed in randomized polynomial time.

#### Oriented Matroids.

One might wonder why we jumped from realizability of matroids to realizability
of abstract order types, instead of using the perhaps closer notion of
oriented matroids [11], for which one can also define a realizability problem
and investigate its complexity. The reason is that in our arguments, we reason
extensively with point configurations, and the geometric interpretation
described above does not adapt directly to oriented matroids, as scaling a
column by a negative number could lead to a change of the underlying oriented
matroid. The correct framework to connect oriented matroids to point
configurations is to only consider _acyclic_ oriented matroids [11, Section
1.2.b], that is, those for which the geometric interpretation works readily
without a need for rescaling by a negative number. This notion of acyclic,
oriented matroids coincides with the notion of abstract order types, and so do
their realizability problems. Note that in some of the existing literature,
oriented matroids and abstract order types are sometimes described as
equivalent. Therefore, we wanted to pay attention to this subtle difference.

#### The existential theory of the reals.

The complexity class $\exists\mathbb{R}$ (pronounced as ‘ER’, ‘exists R’, or
‘ETR’) has gained a lot of interest in recent years. It is defined via its
canonical complete problem ETR (short for _Existential Theory of the Reals_.
ETR refers to a geometric problem and $\exists\mathbb{R}$ refers to the
complexity class. While there are several different variants of ETR, there is
only one complexity class.) and contains all problems that polynomial-time
many-one reduce to it. In an ETR instance, we are given a sentence of the form

$\exists x_{1},\ldots,x_{n}\in\mathbb{R}:\varphi(x_{1},\ldots,x_{n}),$

where $\varphi$ is a well-formed and quantifier-free formula consisting of
polynomial equations and inequalities in the variables and the logical
connectives $\\{\land,\lor,\lnot\\}$. The goal is to decide whether this
sentence is true. As an example consider the formula $\varphi(X,Y):\equiv
X^{2}+Y^{2}\leq 1\land Y^{2}\geq 2X^{2}-1$; among (infinitely many) other
solutions, $\varphi(0,0)$ evaluates to true, witnessing that this is a yes-
instance of ETR. We use $|\varphi|$ to denote the length of $\varphi$, that
is, the number of bits necessary to write down $\varphi$. The solution set of
an ETR-formula is called a semi-algebraic set. The (bit)-complexity of a semi-
algebraic set is the shortest length of any formula defining the set. It is
known that

$\textrm{NP}\subseteq\exists\mathbb{R}\subseteq\textrm{PSPACE}\text{.}$

Here the first inclusion follows because a SAT instance can trivially be
written as an equivalent ETR instance. The second inclusion is highly non-
trivial and was first proven by Canny in his seminal paper [18].

Note that the complexity of working with continuous numbers was studied in
various contexts. To avoid confusion, let us make some remarks on the
underlying machine model. The underlying machine model for $\exists\mathbb{R}$
(over which sentences need to be decided and where reductions are performed)
is the word RAM (or equivalently, a Turing machine) and not the real RAM [24]
or the Blum-Shub-Smale model [12].

The complexity class $\exists\mathbb{R}$ gains its importance by numerous
important algorithmic problems that have been shown to be complete for this
class in recent years. The name $\exists\mathbb{R}$ was introduced by Schaefer
in [52] who also pointed out that several NP-hardness reductions from the
literature actually implied $\exists\mathbb{R}$-hardness. For this reason,
several important $\exists\mathbb{R}$-completeness results were obtained
before the need for a dedicated complexity class became apparent.

Common features of $\exists\mathbb{R}$-complete problems are their continuous
solution space and the nonlinear relations between their variables. Important
$\exists\mathbb{R}$-completeness results include the realizability of abstract
order types [48, 59] and geometric linkages [53], as well as the recognition
of geometric segment [36, 44], unit-disk [34, 46], and ray intersection graphs
[19]. More results appeared in the graph drawing community [22, 23, 41, 54],
regarding the Hausdorff distance [33], regarding polytopes [21, 51], the study
of Nash-equilibria [6, 9, 10, 25, 55], training neural networks [3, 8], matrix
factorization [20, 56, 57, 58, 61], or continuous constraint satisfaction
problems [47]. In computational geometry, we would like to mention geometric
packing [4], the art gallery problem [2], and covering polygons with convex
polygons [1].

Recall that NP is usually described using a witness and a verification
algorithm. The same characterization exists for $\exists\mathbb{R}$. Instead
of the witness consisting of binary words of polynomial length, we allow in
addition using real-valued numbers as a witness. Furthermore, in order to be
able to use those real numbers, we are allowed to work on the so-called real
RAM model of computation. The real RAM allows arithmetic operations with real
numbers in constant time [24].

#### Topological Universality.

Many results and techniques on the existential theory of the reals actually,
precede the study of this complexity class. The underlying idea was to study
how complicated solution spaces can be from a topological perspective. For
example, if we want to study convex polytopes, we are often interested in the
properties of their face lattice. The face lattice is a purely combinatorial
object. Therefore, it is natural to ask which face lattices are realizable by
polytopes. If there would exist an easy combinatorial description of
realizable face lattices, convex polytopes could be much better understood.
Given a specific face lattice $L$, we can study its suitably defined solution
space $S(L)$. As the realizability question can be formulated as an ETR-
formula, it follows that $S$ is a semi-algebraic set. Now, let $T$ be a
different semi-algebraic set, we wonder whether there exists a face lattice
$L$ such that $S(L)$ is homotopy-equivalent to $T$. Maybe surprisingly
topological universality states that there is such an $L$ for any semi-
algebraic set $T$. This type of property feels very strong, as it intuitively
states that we need to encode the vast complexity of semi-algebraic sets into
the problem of realizing convex polytopes. Indeed, many of the results that
establish such topological universality results also imply
$\exists\mathbb{R}$-completeness [44].

However, topological universality can also be established for NP-complete
problems as has been shown by Bertschinger, El Maalouly, Miltzow, Schnider,
and Weber [7]. As the authors showed it is sufficient to encode the topology
of simplicial complexes, as it is possible to triangulate semi-algebraic sets
[27]. In other words, the difference between the wild semi-algebraic sets and
the tame simplicial complexes is not that they emit a more complicated
topological structure. The difference comes from the ability of semi-algebraic
sets to encode complicated topological spaces in a much more concise manner.
(To be precise the description complexity of a topological space might be
exponentially smaller using the language of semi-algebraic sets, compared to
simplicial complexes.) $\exists\mathbb{R}$-completeness can be interpreted as
giving a concise encoding of semi-algebraic sets into a different domain. To
make our life easier, we don’t care about the complete preservation of the
complete topology, but merely of the property of being empty or not. Still, in
order to do so one usually also preserves topological properties. This is the
reason why there is a close connection between topological universality and
$\exists\mathbb{R}$-completeness. But given that NP-complete problems may also
admit universality theorems $\exists\mathbb{R}$-completeness may arguably be
considered the more interesting finding.

#### Stronger Universality Results.

We want to point out that previous universality results often also showed
stronger results than mere topological universality. For instance, Richter-
Gebert showed such a stronger universality theorem for polytopes [51].
Specifically, let $P$ be a polytope, then the face lattice is the family of
faces of different dimension together with their inclusion order. Given a face
lattice $F$, we can define the set of polytopes $V(F)$ having face lattice
$F$. Richter-Gebert showed that for every semi-algebraic set $S$ there exists
the face-lattice $F$ of a polytope such that $V(F)$ is stably-equivalent to
$S$. To define the notion of stable-equivalence goes above the scope of this
paper. It is interesting to note that stable-equivalence encapsulates more
than just the topology of $S$, but also to a degree the “geometry” of $S$.

### Discussion on Input Matroid Encodings

In this paper, we study the $\mathbb{R}$-realizability, where the input
matroid is given with all bases (maximal independent sets). This would seem
unconventional at first glimpse, especially for those familiar with matroid
theory. We would like to address the subtleties around our problem setting.

#### Types of encodings.

For matroids, three possible descriptions are examined in the literature,
namely an explicit description of sets, a description via an oracle, and a
succinct description with a matrix.

Recall that an input graph for a graph problem can be given as an adjacency
matrix, or equivalently the family of vertex subsets of size two. Similarly,
an input hypergraph is typically given as a set family with an explicit
description of all hyperedges. An immediate analogue of such an hypergraph
description for a matroid is an explicit enumeration of all bases (maximal
independent sets) or all circuits (minimally dependent sets). However,
explicitly stating all independent sets, bases, or circuits is unconventional;
the most common size measure of a matroid is the number of elements, which is
polynomially bounded by the size of a graph or matrix that is generalized by a
matroid. On the other hand, the number of bases or circuits can be
prohibitively large in comparison to the number of elements. Specifically, it
is known that the number of distinct matroids on $n$ elements is doubly
exponential in $n$ [35], hence in space of size polynomial in $n$ one cannot
describe an arbitrary input matroid. For further details about explicit
matroid encoding, see [45].

When the matroids under consideration are representable over a field
$\mathbb{F}$, a matrix over $\mathbb{F}$ provides a succinct description of a
matroid. There are well-studied matroid classes that are representable such as
uniform matroids, graphic matroids, and transversal matroids. However, not all
matroids are representable. Hence, an important question is to decide whether
an input matroid is representable over a specific field, or over any field at
all, and to find a representation if one exists.

Due to the limitations of the above two explicit descriptions, the most common
way to encode an input matroid without any restriction is with an oracle,
often with an independence oracle. One can view an independence oracle as a
black box expressing a boolean function on $n$ variables. The boolean function
is on $n$ input variables and outputs 0 or 1 depending on whether the input
corresponds to (a characteristic vector of) an independent set of the said
matroid. Problems with black box functions, an implicit input with oracle
access are studied in the context of learning a function with a small number
of queries, e.g. Polynomial Identity Testing, and also in the context of
search problems where a graph is accessed by adjacency query. Such a problem
does not fit in the classic computational complexity, where an explicit string
of numbers is expected as an input. Moreover, learning a black box (boolean)
function cannot be done efficiently. As mentioned previously, even when the
input boolean functions are restricted to be matroid oracles, deciding whether
a nontrivial matroid property holds or not requires $2^{\Theta(n)}$ queries
[60] even for basic properties such as connectivity and representability over
$\mathbb{F}=GF(2)$, and even with a randomized algorithm.

Therefore, an oracle encoding for $\mathbb{F}$-representability problem does
not appear to be a fruitful setting to better understand the algorithmic
aspects of the problem. Moreover, we shall argue below that, with an explicit
matroid description, there is an intriguing difference in the computational
complexity of $\mathbb{F}$-representability between the cases when
$\mathbb{F}$ is finite and when $\mathbb{F}$ =$\mathbb{R}$.

####  $\mathbb{F}$-representability with explicit bases description.

Let us consider a matroid description that provides a matroid $M$ as a pair
$(E,\mathcal{B})$, where all bases of $M$ are stated in the collection
$\mathcal{B}$. In this setting, we shall argue that the problem of deciding
whether $M$ is $\mathbb{F}$-representable is in NP for a finite field
$\mathbb{F}$ and in $\exists\mathbb{R}$ for $\mathbb{F}=\mathbb{R}$. We shall
also argue that $\mathbb{F}$-representability is likely to be in co-NP for a
finite field $\mathbb{F}$. This makes an interesting contrast with the case
$\mathbb{F}=\mathbb{R}$, for which the corresponding non-representability
problem is unlikely to be in ETR due to our main result.

First, let us see that $\mathbb{F}$-reprsentability is in NP for finite
$\mathbb{F}.$ Indeed, a matrix $A$ (whose columns are labeled by the elements
of $E$) over $\mathbb{F}$ with $M[A]=M$ can be taken as a witness for
$\mathbb{F}$-representability of $M$. Moreover, one can conceive a polynomial-
time verification algorithm for the pair $M=(E,\mathcal{B})$ and $A$ as
follows. Let ${\mathcal{B}}(A)$ be the set of bases of $M[A]$ and recall that
$M=M[A]$ if and only if $\mathcal{B}={\mathcal{B}}(A)$. Whether
$\mathcal{B}\subseteq{\mathcal{B}}(A)$ can be easily verified in time
polynomial in $|\mathcal{B}|+{\sf rk}(M)$. For this, we first compute the
column rank of $A$. If it is different from ${\sf rk}(M)$, this trivially
implies $M[A]\neq M$. Henceforth, let us assume that the column rank of $A$
equals ${\sf rk}(M).$ Now, for each basis $B\in\mathcal{B},$ one checks
whether the submatrix $A[E,B]$, the submatrix of $A$ consisting of all columns
labeled by the elements of $B$, is full rank. If any $B\in\mathcal{B}$ fails
the test, we know that $A$ is not a representation of $M$.

Therefore, we may assume that $\mathcal{B}\subseteq{\mathcal{B}}(A)$. To
verify whether the equality holds, we rely on the following property, which is
easily derived from the Basis Exchange Property. We include its proof in the
appendix for self-containment.

> ($\star$) If ${\mathcal{B}}\subsetneq{\mathcal{B}}(A),$ then there exists
> $B\in\mathcal{B}$ and
> $B^{\prime}\in{\mathcal{B}}(A)\setminus\mathcal{B}^{\prime}$ such that
> $|B\triangle B^{\prime}|=2.$

######  Lemma 4.

Let $\mathcal{B}$ be the set of all bases of a matroid $M$ and let
$\mathcal{B}^{\prime}\subsetneq\mathcal{B}.$ Then there exist bases
$B^{\prime}\in\mathcal{B}^{\prime}$ and
$B\in\mathcal{B}^{\prime}\setminus\mathcal{B}$ with $|B^{\prime}\triangle
B|=2.$

###### Proof.

Choose $B^{\prime}\in\mathcal{B}^{\prime}$ and
$B\in\mathcal{B}\setminus\mathcal{B}^{\prime}$ so that $|B^{\prime}\cap B|$ is
maximized. Let $x\in B^{\prime}\setminus B.$ Recall the Basis Exchange
Property:

> For any distinct bases $W^{\prime},W$ of a matroid and an element $x\in
> W^{\prime}\setminus W$, there exists an element $y\in W\setminus W^{\prime}$
> such that $W^{\prime}-x+y$ is a basis of the matroid.

By the Basis Exchange Property, there exists $y\in B\setminus B^{\prime}$ such
that $B^{\prime\prime}:=B^{\prime}-x+y$ is a basis of $M.$ If
$B^{\prime\prime}$ belongs to $\mathcal{B}^{\prime},$ we have
$B^{\prime\prime}\cap B=(B^{\prime}\cap B)+y$, which contradicts the choice of
$B^{\prime}$ and $B.$ Therefore, $B^{\prime\prime}$ belongs to
$\mathcal{B}\setminus\mathcal{B}^{\prime}.$ Note that $|B^{\prime}\cap
B^{\prime\prime}|=|B^{\prime}-x|=r-1$ and (thus $B^{\prime\prime}=B$ by the
choice of $B^{\prime}$ and $B$) and the claim follows. ∎

Hence, the last step of the verification algorithm tests if there exist a
basis $B\in\mathcal{B}$ and two element $x\in B$ and $y\in E-B$ such that
$B-x+y$ is not a basis of $M$ but the corresponding set of columns of $A$ is
independent, which precisely tests if
$B-x+y\in\mathcal{B}(A)\setminus\mathcal{B}$. If such a triple $B,x,y$ exists,
clearly $\mathcal{B}\subsetneq{\mathcal{B}}(A)$ and thus $M[A]\neq M.$
Conversely if $\mathcal{B}\subsetneq{\mathcal{B}}(A),$ there exist such a
triple $B,x,y$ by Property ($*$). Therefore, we examine all triples $(B,x,y)$
with $B\in\mathcal{B}$, $x\in B$ and $y\in E-B$ and certify that $B-x+y$ is
either in $\mathcal{B}$ or dependent, in which case the verification algorithm
can correctly conclude that $\mathcal{B}(A)=\mathcal{B}$, thus $M[A]=M.$
Otherwise, the verification algorithm concludes $M[A]\neq M$ and rejects the
witness $A$.

The presented verification algorithm shows that $\mathbb{F}$-representability
is in NP for each finite field $\mathbb{F}.$ A matrix over $\mathbb{F}$ as
witness and the polynomial-time verification algorithm naturally extend to the
case when $\mathbb{F}=\mathbb{R}$, where the verification algorithm works on a
real RAM. Therefore, $\mathbb{R}$-representability is in $\exists\mathbb{R}$.
For details on the characterization $\exists\mathbb{R}$ via a witness and a
polynomial-time verification algorithm on a real RAM, see [24], and also the
discussion in the paragraph above about the existential theory of the reals.

Furthermore, it is likely that $\mathbb{F}$-representability is in co-NP for
each finite field $\mathbb{F}.$ It is known [26] that for any prime field
$\mathbb{F}$, non-$\mathbb{F}$-representability can be certified by evaluating
the ranks of $O(n^{2})$ subsets of an $n$-element matroid. Notice that when
the matroid $M=(E,\mathcal{B})$ is given with an explicit description of all
the bases $\mathcal{B}$ of $M$, evaluating ${\sf rk}(X)$ for $X\subseteq E$
can be done in time polynomial in the input size because ${\sf rk}(X)$ equals
the maximum of $|X\cap B|$ over all $B\in\mathcal{B}.$ Therefore,
$\mathbb{F}$-representability is in co-NP under the explicit bases description
for each prime field $\mathbb{F}.$ For an arbitrary finite field $\mathbb{F}$,
not necessarily prime, up to our best knowledge there is no published result
which establishes that a polynomial number of rank evaluations suffices for
non-$\mathbb{F}$-representability. However, it is known that a positive
resolution of Rota’s conjecture implies that only a constant, depending on
$|\mathbb{F}|$ only, number of rank evaluations would suffice [50] to certify
that a given matroid is not $\mathbb{F}$-representable. The proof of Rota’s
conjecture was announced in 2014 by Geelen, Gerards and Whittle [32] although
it is expected to take a few more years for the full proof to be written for
publication.

Therefore, $\mathbb{F}$-representability appears to be in NP $\cap$ co-NP when
the input is given as the exhaustive list of bases for each finite
$\mathbb{F}$ given the claimed proof of Rota’s conjecture. Given that,
deciding the computational complexity of $\mathbb{F}$-representability for
each finite $\mathbb{F}$ with explicit bases description is an intriguing
question. For $\mathbb{F}=GF(2),$ a polynomial-time algorithm is
straightforward from the uniqueness of a binary representation (up to linear
transformation) and the fact that such a representation can be efficiently
obtained [50]; after constructing a matrix over $GF(2)$, we apply the above
verification algorithm for NP membership. However, even for $\mathbb{F}=GF(3)$
it is not clear whether a matrix over GF(3) can be efficiently constructed
although it is known that there is a unique representation over $GF(3)$ for a
matroid representable over $GF(3).$ As far as we are aware, there is no
efficient procedure known for constructing the representation of a matroid $M$
with a promise that $M$ is representable over $GF(3),$ when $M$ is given with
an independence oracle or even given as a matrix over the rationals
$\mathbb{Q}$ [28]. Getting an input matroid as explicit bases description
might help to circumvent this obstacle.

In contrast to the case of finite field, it is impossible to certify
non-$\mathbb{R}$-representability with a polynomial number of rank evaluations
[50]. Finally, for $\mathbb{R}$-representability we showed that
$\exists\mathbb{R}$-complete, exhibiting a noticeable diversion from
$\mathbb{F}$-representability for finite $\mathbb{F}$ which appears neither
NP-complete nor co-NP-complete with explicit bases description under the
assumption NP $\neq$ co-NP. Therefore, our result highlights the recurring
contrast between representability over finite field and over the reals.

##  2 Distinct-ETR

This section serves as a preparation for the later reduction. Specifically, we
show $\exists\mathbb{R}$-completeness of a variant of ETR. We name this
variant Distinct-ETR, as we can assume that there is a solution with all
variables holding distinct values. This property will be key for encoding into
matroids. Most of this section follows standard techniques.

#### Overview.

This section is dedicated to the proof of the lemma. The idea is that we first
establish the hardness of an ETR variant (STRICT-INEQ) with an open solution
space. It is clear that all variables can be assumed there to have distinct
values. Then, we reduce again to a variant where we use only the basic
constraints.

The reduction goes in four steps.

  1. 1.

From ETR to ETRAMI.

  2. 2.

Then from ETRAMI to Feasibility.

  3. 3.

Then from Feasibility to STRICT-INEQ.

  4. 4.

And at last from STRICT-INEQ to Distinct-ETR.

Note that step 1,2, and 3 have already been done (among others) by Schaefer
and Štefankovič [55]. We sketch the main steps of their reduction.
Specifically, we point out some properties that were not explicitly
emphasized. We start to explain a simple trick that is excessively used in
those types of constructions in order to build small, very small, and very
large numbers.

#### Number Constructions.

Before we describe the reduction it might be useful to understand how we can
construct variables that must have specific rational values.

If we want to build integers of polynomial size, we can do this by simply
repeatedly adding or subtracting a one.

$a_{1}=1,\quad a_{i+1}=a_{i}+a_{1},\quad a_{i-1}+a_{1}=a_{i}.$

It is easy to see that $a_{i}=i$, for all $a_{i}$ that are defined in this
way.

If we want to build a very large number, say $2^{2^{k}}$, the previous
approach cannot be done in polynomial time. Instead, we can use repeated
squaring as follows.

$x_{0}=a_{2}+a_{0}(=2),\quad x_{i+1}=x_{i}^{2},$

for $i=1,\ldots,k$. It holds inductively that $x_{i}=2^{2^{i}}$. Similarly, we
can construct very small numbers say $2^{2^{-k}}$, as follows:

$x_{0}+x_{0}=1,\quad x_{i+1}=x_{i}^{2},$

for $i=1,\ldots,k$. It holds inductively that $x_{i}=2^{-2^{i}}$. Note that we
can also use strict inequalities to build large and small numbers. For
example,

$x_{0}>2,\quad x_{i+1}>x_{i}^{2},$

for $i=1,\ldots,k$ implies that $x_{i}>2^{2^{i}}$.

We will use these standard tricks repeatedly later in the reduction.

#### Reduction from ETR to ETRAMI.

We define the problem ETRAMI as a variant of ETR as follows. We are given
variables $X=\\{x_{1},\ldots,x_{n}\\}$ and constraints of the form

$x+y=z,\quad x\cdot y=z,\quad x=1,$

for $x,y,z\in X.$ Therefore, ETRAMI is a variant of ETR without negations,
inequalities, disjunctions, conjunctions and the only constant is $1$. It is
folklore that ETRAMI is $\exists\mathbb{R}$-complete and follows implicitly
from various papers [44, 55, 59]

######  Lemma 5 (folklore).

ETRAMI is $\exists\mathbb{R}$-complete.

$\exists\mathbb{R}$-membership follows from the definition. The idea of the
reduction is to simplify an ETR-formula in each step. For instance, we can
remove negations by replacing $\lnot p>0$ by $p\leq 0$. In this way, we can
remove all negations. We can replace inequalities by observing that $p\geq 0$
is equivalent to $\exists x:p=x^{2}$ and $p>0$ is equivalent to $\exists
x:px^{2}=1$. We can replace $p=0\land q=0$ by $p^{2}+q^{2}=0$. Similarly, we
can replace $p=0\lor q=0$ by $pq=0$. Thereafter, we end with a single
polynomial equation $p=0$. We construct variables for each coefficient value.
Then we replace each coefficient with an appropriate variable. At last, we
replace each occurrence of multiplication and addition inductively by
introducing one more variable and one more constraint. We end with a single
equation of the form $x=0$, which can be replaced by $z=1$ and $z+x=z$.

#### Reduction from ETRAMI to Feasibility.

In Feasibility, we are given a single polynomial
$p\in\mathbb{Z}[x_{1},\ldots,x_{n}]$ of degree at most four. We are asked if
there exists some $x\in\mathbb{R}^{n}$ such that $p(x)=0$. Furthermore, we
require each coefficient to be of absolute value at most $36n^{3}$. Below, we
will show how to achieve this upper bound.

######  Lemma 6.

Feasibility is $\exists\mathbb{R}$-complete.

Again, $\exists\mathbb{R}$-membership follows from the fact that Feasibility
is a special case of ETR. To show hardness we sketch a reduction from ETRAMI
that is already known [44, 55]. Let $f_{1}=0,\ldots,f_{m}=0$ be the
constraints of some ETRAMI instance $\varphi$. (For example $x+y=z$ becomes
$x+y-z=0$.) Let

$p=f_{1}^{2}+\ldots+f_{m}^{2}.$

Clearly, $\varphi$ is satisfiable if and only if $p$ has a zero. As each
$f_{i}$ has a degree at most two it holds that $p$ has degree at most four. As
there are only $3n^{3}$ possible distinct constraints in $\varphi$, we have
$m\leq 3n^{3}$. Note that each term $f_{i}^{2}$ gives rise to at most six
monomials and each coefficient is at most two. (For example
$(x+y-z)^{2}=x^{2}+2xy-2xz+y^{2}-2yz+z^{2}$.) Therefore each coefficient has
absolute value at most $12m=36n^{3}$. Thus, we can rewrite $p$ as a sum of
monomials with bounded-sized coefficients, as claimed.

#### Reduction from Feasibility to STRICT-INEQ.

In a STRICT-INEQ instance, we are given a sentence of the form

$\exists x_{1},\ldots,x_{n}\in\mathbb{R}:\varphi(x_{1},\ldots,x_{n}),$

where $\varphi$ is a well-formed and quantifier-free formula consisting of
polynomial strict-inequalities in the variables and the logical connectives
$\\{\land,\lor\\}$.

Note that the solution space $\\{x\in\mathbb{R}^{n}:\varphi(x)\\}$ is always
open.

######  Lemma 7.

STRICT-INEQ is $\exists\mathbb{R}$-complete.

Again membership follows from the fact that ETR is more general then STRICT-
INEQ. To show $\exists\mathbb{R}$-hardness we reduce from Feasibility. The
idea of the reduction is to replace $p(x)=0$ by $-\delta<p(x)<\delta$, for
some sufficiently small $\delta$. To this end, we employ two lemmas as
formulated by Schaefer and Štefankovič [55]. Note that the actual proof comes
from real algebraic geometry and can be read for instance in [5] and [31].

######  Lemma 8.

Every non-empty semi-algebraic set in $\mathbb{R}^{n}$ of complexity at most
$L\geq 4$ contains a point of distance at most $2^{L^{8n}}$ from the origin.

######  Lemma 9.

If two semi-algebraic sets in $\mathbb{R}^{n}$ each of complexity at most
$L\geq 5n$ have positive distance (for example, if they are disjoint and
compact), then that distance is at least $2^{-2^{L+5}}$ .

In this context the distance between two sets $A,B$ is defined as

$d(A,B)=\inf_{a\in A,b\in B}\|a-b\|.$

Note that $\|\cdot\|$ denotes the Euclidean norm.

In order to apply Lemmas 8 and 9, we define the following three semi-algebraic
sets. First, we define the solution set for $p$.

$S=\\{x\in\mathbb{R}^{n}:p(x)=0\\}.$

Let $R=2^{L^{8n}}$, where $L$ is the bit-complexity of $S$. Note that $L$ is
the upper bound by the length of $p$. Using Lemma 8, we know that $S$ is empty
if and only if $S\cap B(R)$ is empty. (We denote by $B(R)$ the ball of radius
$R$ around the origin.) This motivates us to define the sets

$S_{1}^{\prime}=\\{(x,z)\in\mathbb{R}^{n+1}:p(x)=z\land\|x\|^{2}\leq
R^{2}\\},$

and

$S_{2}^{\prime}=\\{(x,z)\in\mathbb{R}^{n+1}:z=0\land\|x\|^{2}\leq R^{2}\\}.$

Note that $S_{1}^{\prime}\cap S_{2}^{\prime}=(S\cap B(R))\times\\{0\\}$.
Furthermore, $S_{1}^{\prime}$ and $S_{2}^{\prime}$ are compact and thus we can
apply Lemma 9. Unfortunately, the description complexity of $S_{1}^{\prime}$
and $S_{2}^{\prime}$ are exponential, if we write $R$ out in binary.
Therefore, we define $S_{1}$ and $S_{2}$ slightly differently. Namely, we add
some extra variables, whose sole purpose is to encode $R$ using repeated
squaring. Let $\overline{L}$ be the max of the bit complexity of $S_{1}$ and
$S_{2}$. Note that $\overline{L}=O(L+n\log L)$. Let $\delta$ be as in Lemma 9
applied to $S_{1}$ and $S_{2}$. It holds that $S=\emptyset$ is equivalent to
$S\cap B(R)=\emptyset$. This in turn is equivalent to $S_{1}\cap
S_{2}=\emptyset$. And this is equivalent to

$p(x)\leq-\delta\text{ or }\delta\leq p(x),$

for all $x\in B(R)$. In other words, we have

$\exists x:\ -\delta<p(x)<\delta\text{ and }\|x\|^{2}<R^{2}$ (1)

if and only if

$\exists x:\ p(x)=0$

This obviously also works if we would use any smaller $\delta$. Maybe not so
obviously, this also works for $R$ of between $2^{L^{8n}}$ and $2^{L^{8n+1}}$.
The lower bound allows us to apply Lemma 8. The upper bound allows us to apply
Lemma 9. Using repeated squaring, we create numbers $a>2^{L^{8n}}$ and
$b<2^{L^{8n+1}}$. Furthermore, we add the inequalities $a<R<b$. Note that we
can construct a number $\delta$ that is at most $2^{-2^{\overline{L}+5}}$. Our
STRICT-INEQ instance $\varphi$ consists of the three inequalities from
Equation 1 and some extra variables and constraints to bound $R$ and $\delta$
as described above.

#### Reduction from STRICT-INEQ to Distinct-ETR.

In this section, we show that Distinct-ETR is $\exists\mathbb{R}$-complete. We
are not actually reducing from STRICT-INEQ but from the instance $\varphi$
described in Equation 1. Let $\delta,R$ be the given numbers,
$x_{1},\ldots,x_{n}$ the variables and $p$ the polynomial as in the previous
paragraph. Recall that $p$ has a degree at most four and the coefficients are
bounded integers. We will introduce new variables in order to construct
$\delta$, $R$, $\|x\|^{2}$, and $p(x)$. Thereafter, we will argue about
distinctness.

First, we construct variables holding the values of the integers
$-36n^{3},\ldots,36n^{3}$. Those variables are meant to represent the
coefficients of $p$. Recall that this was an upper bound on the values of
those coefficients. It has been described above how to construct those
integers. Furthermore, we add variables holding the values $R=2^{L^{8n}}$ and
$\delta=2^{-2^{\overline{L}+5}}$. (As we reduce from Equation 1, we do not
need to approximate the values $\delta$ and $R$, but can construct them
directly, as Distinct-ETR allows us to use equations.) If in this process two
variables hold the same value, we can detect this and remove one of the
variables.

Now, we construct $p(x)$ and $\|x\|^{2}$. First, we construct all possible
$\binom{n}{4}$ monomials of degree at most four. For example, $N=xyzw$ is
constructed in three steps. $N_{1}=xy$, $N_{2}=N_{1}z$, and $N=N_{2}w$. Again,
whenever two identical monomials would appear, we would be able to notice this
and make an appropriate replacement. Let us denote

$p(x)=\sum_{i=1}^{m}a_{i}M_{i}.$

Here, $a_{i}$ is the coefficient of the monomial $M_{i}$. We construct
$P_{k}=\sum_{i=1}^{k}a_{i}M_{i}$ inductively as follows:

$P_{1}=a_{1}M_{1}\text{ and }P_{k}=P_{k-1}+T_{k},$

with $T_{k}=a_{k}M_{k}$.

We denote by $P=P_{m}$ the variable holding the value of $p(x)$. We also
construct $X=\|x\|^{2}=x_{1}^{2}+\ldots+x_{n}^{2}$ in the same way.

At last, we add the variables $a,b,c$, and the constraints

$a+\delta=P,\quad b+P=\delta,\quad c+X=R.$

Now we can enforce the inequalities

$\ -\delta<p(x)<\delta\text{ and }\|x\|^{2}<R^{2}$

by

$a>0,\quad b>0,\quad c>0.$

To summarize, we started with the variables $x_{1},\ldots,x_{n}$. We have
created variables $C_{1},\ldots,C_{s}$ that each holds a different
integer/rational number. Furthermore, we constructed some variables
$V_{1},\ldots,V_{t}$ such that each $V_{i}$ is a polynomial function
$g_{i}(x)$. Note that all the $g_{i}$ have a degree of at most four and small
integer coefficients. If for two variables $V_{i}$ and $V_{j}$, we have that
$g_{i}=g_{j}$, we can detect this and remove one of them and replace each
occurrence with the other one. This finishes the description of the reduction.
We denote this instance $\psi$. It remains to argue correctness.

To show correctness, we observe that $\varphi$ has a solution if and only if
$\psi$ has a solution as well. Indeed, all new variables and constraints only
“build” the correct polynomials and the numbers $\delta,R$. Thus it remains to
show that if $\varphi$ has a solution if and only if $\psi$ has a solution
with all variables taking distinct values. The backward direction is trivial.
Therefore, we assume that $\varphi$ has at least one solution
$x\in\mathbb{R}^{n}$. As the solution space of $\varphi$ is open, there is an
open ball fully contained in the solution space. Clearly, the variables
$C_{1},\ldots,C_{s}$ have all fixed distinct values by construction. Every
other variable $V_{i}$ can be expressed as a polynomial function $g_{i}(x)$.
As all the $g_{i}$ are distinct there must be some $x\in B$ such that
$g_{i}(x)\neq g_{j}(x)$, for all $i\neq j$ and $g_{i}(x)\neq C_{j}$, for all
$i,j$. Otherwise, two of the polynomials would be identical. This finishes the
proof.

##  3 Arithmetic using Matroids

In this section, we describe how to encode addition and multiplication of real
numbers using rank-$3$ matroids. We rely on the _von Staudt constructions_ ,
which are very well-known, perhaps with the caveat that they are usually
stated for oriented matroids. But as we shall see, no orientedness is actually
required to make them work. We follow the presentation of Matoušek [44].

The setup for both operations is as follows. We have a line $\ell$ containing
three distinct distinguished points called $\mathbf{0}$, $\mathbf{1}$, and
$\mathbf{\bm{\infty}}$, and a fixed second line $\ell_{\infty}$ crossing
$\ell$ at $\mathbf{\bm{\infty}}$. Given the variable $x$, we denote the
corresponding point representing it by $\mathbf{x}$ in fat. This way we easily
distinguish between a point and the corresponding variable. A point
$\mathbf{x}$ on the line $\ell$ can be interpreted as a real number using
cross-ratios: if we denote by $d(\mathbf{a},\mathbf{b})$ the oriented distance
between two points $\mathbf{a}$ and $\mathbf{b}$ on the line $\ell$, then the
quantity

$(\mathbf{x},\mathbf{1};\mathbf{0},\mathbf{\bm{\infty}}):=\frac{d(\mathbf{x},\mathbf{0})\cdot
d(\mathbf{1},\mathbf{\bm{\infty}})}{d(\mathbf{x},\mathbf{\bm{\infty}})\cdot
d(\mathbf{1},\mathbf{0})}$

is a real number invariant under projective transformations, which, by a
slight abuse of notation, we simply denote by $x$. Note that if
$\mathbf{\bm{\infty}}$ is progressively sent to infinity using a projective
transformation and $d(\mathbf{0},\mathbf{1})$ is scaled to one in this
formula, $x$ converges to $d(0,x)$. Thus this cross-ratio matches the
geometric location of $\mathbf{x}$ on $\ell$ under some projective
transformation.

Now, given two points $\mathbf{x}$ and $\mathbf{y}$ on $\ell$, we describe
geometric operations to compute points on the line $\bm{x+y}$ and $\bm{x\cdot
y}$ on $\ell$ representing their addition and their multiplication.

$\mathbf{\bm{\infty}}$
---
$\mathbf{0}$
---
$\mathbf{x}$
---
$\mathbf{y}$
---
$\mathbf{x}+\mathbf{y}$
---
$\mathbf{a}$
---
$\mathbf{b}$
---
$\ell_{\infty}$
---
$\ell$
---
$\mathbf{0}$
---
$\mathbf{x}$
---
$\mathbf{y}$
---
$\mathbf{x}+\mathbf{y}$
---
$\mathbf{c}$
---
$\mathbf{d}$
---
$\ell$
---
$\mathbf{c}$
---
$\mathbf{d}$
---
Figure 3: Encoding addition geometrically

#### Addition.

The construction is pictured in Figure 3, left. We first introduce two
distinct auxiliary helper points $\mathbf{a}$ and $\mathbf{b}$ situated
anywhere on $\ell_{\infty}$. The line connecting $\mathbf{0}$ to $\mathbf{b}$
crosses the line connecting $\mathbf{x}$ to $\mathbf{a}$ in a point
$\mathbf{c}$, then the line connecting $\mathbf{\bm{\infty}}$ to $\mathbf{c}$
crosses the line connecting $\mathbf{y}$ to $\mathbf{b}$ in a point
$\mathbf{d}$. Similarly, the line connecting $\mathbf{a}$ to $\mathbf{d}$
crosses $\ell$ in a point that we define to be $\bm{x+y}$. The rationale
behind this construction is that by a projective transformation we can
consider $\ell_{\infty}$ to be a line at infinity, bringing us the Figure 3,
right. Now the line containing $\mathbf{c}$ and $\mathbf{d}$ crosses $\ell$ at
a point at infinity, i.e., these two lines are parallel. Likewise, the line
containing $c$ and $d$ is parallel to $\ell$. Then the parallelity of the
lines immediately shows that
$d(\mathbf{0},\bm{x+y})=d(\mathbf{x},\mathbf{y})+d(\mathbf{0},\mathbf{y})$. In
other words, the point $\bm{x+y}$ has value $x+y$, justifying the notation.

$\mathbf{\bm{\infty}}$
---
$\mathbf{0}$
---
$\mathbf{x}$
---
$\mathbf{y}$
---
$\mathbf{x}\mathbf{y}$
---
$\mathbf{a}$
---
$\mathbf{b}$
---
$\ell_{\infty}$
---
$\ell$
---
$\mathbf{0}$
---
$\mathbf{x}$
---
$\mathbf{y}$
---
$\mathbf{x}\mathbf{y}$
---
$\mathbf{c}$
---
$\mathbf{d}$
---
$\mathbf{1}$
---
$\ell$
---
$\mathbf{c}$
---
$\mathbf{d}$
---
$\mathbf{1}$
---
Figure 4: Encoding multiplication geometrically

#### Multiplication.

The construction is pictured in Figure 4, left. As before, we first introduce
two distinct auxiliary helper points $\mathbf{a}$ and $\mathbf{b}$ situated
anywhere on $\ell_{\infty}$. The line connecting $\mathbf{1}$ and $\mathbf{b}$
crosses the line connecting $\mathbf{x}$ and $\mathbf{a}$ at a point
$\mathbf{c}$, and the line connecting $\mathbf{0}$ and $\mathbf{c}$ crosses
the line connecting $\mathbf{b}$ and $\mathbf{y}$ at a point $\mathbf{d}$.
Finally, the line connecting $\mathbf{a}$ and $\mathbf{d}$ crosses the line
$\ell$ at a point that we define to be $\bm{xy}$. By sending the line
$\ell_{\infty}$ at infinity using a projective transformation, we obtain
Figure 4, right, where one can readily show using the parallel lines that
$d(\mathbf{0},\bm{xy})=d(\mathbf{0},\mathbf{x})d(\mathbf{0},\mathbf{y})$. In
other words, the point $\bm{xy}$ has value $xy$, justifying the notation.

#### Encoding these geometric constructions using matroids.

The addition and multiplication constructions defined above can be entirely
encoded using matroids: the independent sets are exactly the empty set, all
the singletons, all the pairs of points, and all the triples of non-aligned
points. Let us insist here that no orientation was ever enforced during the
constructions, and thus we do not need oriented matroids to describe them.
Furthermore, these operations can be chained arbitrarily, allowing to encode
polynomials using matroids. However, some very important care needs to be
taken here: while it is clear from the construction which points should be
aligned, we also need to make sure that points that should not be aligned can
be assumed to not be aligned. For example, it could a priori happen that a
line going through two helper points $c_{1}$ and $c_{2}$ somehow accidentally
happens to pass through a variable $x$ of the polynomial we are encoding. In
that case, the matroid would not properly encode the geometric construction.

This motivates the following definition: we say that the set $S$ of helper
points used during an addition or multiplication construction is _free_ if for
any finite set of lines $L$ and points $P$ not involved in the construction,
the points in $S$ can be perturbed so that:

  * •

the incidences required by the addition or multiplication construction still
hold,

  * •

no point of $S$ lies on a line $L$, and

  * •

no pair of points of $S$ is aligned with a point of $P$
(in particular, no point of $S$ coincides with a point of $P$).

A key property of the addition and multiplication construction is that the
four helper points that they rely on form a free set. Indeed, the points $a$
and $b$ can be placed freely on the line $\ell_{\infty}$, and thus can be
perturbed so as to avoid the lines and points of $P$ and $L$. Such a
perturbation induces a perturbation of $c$ and $d$ in a two-dimensional open
set, therefore allowing them to avoid lines of $P$ and $L$, but also ensuring
that no line going through a pair of points in $\\{a,b,c,d\\}$ also goes
through a point in $P$.

This freedom will be leveraged in the proofs of Theorem 2, respectively
Theorem 1, to ensure that the matroid correctly encodes orientation
predicates, respectively systems of polynomial equations.

#### Strict inequalities.

The multiplication construction can be leveraged to simulate a strict
inequality constraint $x>0$. Indeed, $x>0$ if and only if there exists
$z\in\mathbb{R}$ such that $z\neq 0$ and $x=z^{2}=zz$, which can thus be
simulated using a helper point $z$ distinct from $0$ and the above
multiplication construction. However, this construction would require us to
use as a helper point a fixed point $z$ on the line $\ell$, which could not be
perturbed and thus would not be free. This can be resolved by using an
additional variable: we first introduce a helper point $y$ for which we ensure
that $y>0$ using the multiplication gadget. Then we use another multiplication
gadget to ensure that $z>y$: note that this amounts to enforcing that $z$ lies
on the same side of $y$ than $1$ does, i.e., this can be tested by using
another multiplication gadget where $0$ is replaced by $y$. Now, in these two
multiplication gadgets, neither $y$ nor any of the other helper points is
fixed, and therefore we can perturb them to avoid any fixed set of lines and
points, showing that they form a free set of points.

##  4 Proof of Theorem 2

Theorem 2 is proved by using the arithmetic constructions described in the
previous section, in particular the one for strict inequalities, to simulate
orientation predicates.

#### Simulating rank $3$ order types.

We will first consider the case of rank equal to $3$ and treat the general
case later. Let $O=(E,\chi)$ be an order type on $n$ elements of rank $3$.
($E=\\{e_{1},\ldots,e_{n}\\}$.) We construct a matroid $M$ from $O$
inductively. To be more precise, we construct matroids,
$M_{3},M_{4},\ldots,M_{n}=M$ such that $M_{i}$ simulates $O_{i}$. Here,
$O_{i}=(E_{i},\chi_{i})$ is the order type formed by the first $i$ elements of
$O$. All of our matroids $M_{i}$ will feature a distinguished line
$\ell_{\infty}$.

The matroid $M_{3}$ merely contains $e_{1},e_{2},e_{3}$. Without loss of
generality we assume that the triple $t=\\{e_{1},e_{2},e_{3}\\}$ are
independent in $O$. (Otherwise, all triples in $O$ are dependent, which can
trivially be simulated.) We first add a line at infinity, on which no $e_{1}$,
$e_{2}$ or $e_{3}$ lies. We can assume that $t$ is oriented correctly in any
representation of $M_{3}$, as otherwise, we can just reflect the
representation and get a correct representation. Therefore, $M_{3}$ satisfies
the induction hypothesis.

Now, let us assume that we already constructed $M_{i-1}$. We construct $M_{i}$
from $M_{i-1}$, by adding the element $e=e_{i}$ from $O$. Furthermore, for
each triple $t=\\{a,b,e\\}\subset E_{i}$, we need to ensure that $t$ is
oriented correctly. In case that $\chi(t)=0$, we can encode this into $M_{i}$
directly by specifying that $(a,b,e)$ forms a rank-$2$ dependent set. Thus it
remains to consider the case $\chi(t)\neq 0$. Let
$t^{\prime}=\\{a,b,c\\}\subset E_{i-1}$ such that $\chi(t^{\prime})\neq 0$.
Note that such a triple $t^{\prime}$ must exists, as otherwise all points of
$E_{i}$ lie on a common line. This would be a contradiction to the fact that
$M_{3}$ is formed by an independent triple. Using the orientation of
$t^{\prime}$ we add a small constant number of helper points and we will
enforce the correct orientation of $t$ in $M_{i}$ as well. Thus it remains to
show the following lemma, where we use the notion of a free set of helper
points defined in Section 3.

######  Lemma 10.

Given the independent triple $t^{\prime}=\\{a,b,c\\}$ in a matroid $M$ and
another point $e$, we can enforce that in any valid representation of $M$, the
triple $t=\\{a,b,e\\}$ is oriented identically to $t^{\prime}$, or that it is
oriented opposite to $t^{\prime}$. We do this by adding a constant number of
helper points to $M$. Furthermore, this set of helper points is free.

###### Proof.

This construction goes in essentially two steps. First, we show how we can
enforce an element $x$ on the line $\ell=\ell(a,b)$ to be on the same side of
$a$ as $b$.

It relies on standard constructions to do encode arithmetic operations as
explained in Section 3. Although, those constructions can be well described
and understood, without any reference to arithmetic operations, the language
of arithmetic operations gives a better intuition. The underlying idea is that
we interpret $a$ as zero, and $b$ as $1$. Indeed, the constraint that $c$ lies
on the same side of $a$ as $b$ in any representation where the line
$\ell_{\infty}$ is sent to infinity amounts to enforcing that $c>0$ when $a$
is interpreting $a$ as zero and $b$ as one. As explained in Section 3, this
can be encoded using multiplication gadgets, in such a way that none of the
helper points accidentally lies on a previously used line or point.

In the second step, we use the previous tool to enforce that $e$ and $c$ lie
on the same (or the opposite) side of the line $\ell(a,b)$ as $c$.

$a$
---
$d$
---
$b$
---
$c$
---
$c^{\prime}$
---
$e$
---
Figure 5: Forcing $c$ to be on the same side of $\ell(a,b)$ as $e$. Half-open
lines denote the strict inequality constraints.

To this end, we first define a point $c^{\prime}$ for which we enforce that on
the line $\ell(a,c)$, it lies on the same side of $a$ as $c$. Then we define a
point $d$ situated on the line $\ell(a,b)$ and a line $\ell^{\prime}$ with
points $c^{\prime},d,e$. See Figure 5 The condition that $e,c^{\prime}$ are on
the same side of $d$ on the line $\ell^{\prime}$ can be enforced using the
previous gadgets. Furthermore, it is equivalent to $c^{\prime}$ and $e$ being
on the same side of $\ell(a,b)$. Lastly, by construction the triple
$\\{a,b,c^{\prime}\\}$ is oriented identically to $\\{a,b,c\\}$.

We can use the same tool to enforce that $e$ and $c$ lie on the opposite side
of the line $\ell(a,b)$. We define $c^{\prime}$ as before, so that it lies on
the same side of $\ell(a,b)$ as $c$, and then we simply need to enforce
instead that $c^{\prime}$ lies on the same side of $e$ as $d$.

As explained in Section 3, the strict inequalities gadgets can be directly
encoded into the independent sets of the matroid, and by construction, the
helper points always have at least one degree of freedom, and thus can form a
free set of points. Therefore, the matroid $M_{i}$ is entirely defined by the
dependency constraints indicated by the lines in the geometric constructions.
This concludes the proof. ∎

We can now conclude the proof of Theorem 2 for rank-$3$ matroids. Given an
order type $O$ of rank $3$, for which we can assume that there is at least one
independent set of size $3$ (otherwise the orientation predicates are
trivial), we inductively encode the orientation predicates into an matroid
using the helper points provided by Lemma 10. At each stage of the induction,
the freedom of the set of helper points can be used to ensure that the helper
points do not yield any accidental dependencies with all the points and lines
previously placed. At the end of the induction, by Lemma 10, any valid
representation of the resulting matroid $M$ induces a representation of $O$.
Conversely, any representation of $O$ can be extended to a representation of
$M$. Therefore $M$ simulates $O$. All the constructions can clearly be done in
linear time, which concludes the proof.

#### Simulating rank $k$ Matroids.

The construction for rank $k$ is identical to that of rank $3$ as explained
above, with two exceptions. First, the induction basis starts with a matroid
on $k$ elements instead of $3$. Second, we have to describe the simulation of
an oriented $k$-tuple. For this, we use the same trick that forces a point to
lie on a specific side of a line, where we just replace a line with a
hyperplane $P$, as pictured in Figure 6.

$P$
---
$d$
---
$a$
---
$a^{\prime}$
---
$x$
---
$a_{1}$
---
Figure 6: Forcing $x$ to be on the same side of $P$ as $a$.

More precisely, in an inductive step where we add a point $x$, we need to
enforce the orientation of all the independent $k$-tuples $t=\\{a_{1},\ldots
a_{k-1},x\\}$. For this, we take another $k$-tuple $t^{\prime}=\\{a_{1},\ldots
a_{k-1},a\\}$ for which $\chi(t^{\prime})\neq 0$, and we devise a gadget to
encode the constraint that $t$ is oriented identically, or opposite to
$t^{\prime}$. This will be done using the gadget described above that enforces
that in any valid representation, for three aligned points $a,b$ and $c$, $c$
lies on the same side of $a$ as $b$. That gadget was defined for rank $3$
matroids and thus representations into $\mathbb{R}^{2}$, but readily works in
higher dimensions: one should simply ensure using dependency constraints that
all the points involved in the gadget lie on a common plane. The hyperplane at
infinity will intersect this common plane in a line, which takes the role of
the line at infinity in the gadgets.

Now, we proceed as in the rank $3$ case: considering the hyperplane $P$
generated by $\\{a_{1},\ldots a_{k-1}\\}$, we first define a point
$a^{\prime}$ that lies on the same side as $a$ on the line $\ell(a_{1},a)$.
Then we can enforce that $a^{\prime}$ is on the same side of $P$ as $x$ by
introducing the point $d$ at the intersection of $P$ and the line going
through $a^{\prime}$ and $x$. Then we enforce that $x$ is on the same side of
$d$ as $a^{\prime}$. In order to enforce that $a^{\prime}$ and $x$ are on
opposite sides of $P$, we instead enforce that $x$ and $a^{\prime}$ are on
opposite sides of $d$. Finally, we observe that all the helper points that we
have introduced are free, where the notion of freedom is generalized to also
disallow $k$-dimensional dependencies: once again this follows from the fact
that all the helper points that we introduce have some wiggle room to be
perturbed. The rest of the proof proceeds identically to the rank-$3$ case.

##  5 Proof of Theorem 1

The proof of Theorem 1 is by a direct reduction from the problem Distinct-ETR,
using the arithmetic constructions described in Section 3. Let us start with
an instance of Distinct-ETR given by variables $X=\\{x_{1},\ldots,x_{n}\\}$
and constraints of the form

$x+y=z,\quad x\cdot y=z,\quad x=1,\quad x>0,$

for $x,y,z\in X$, with the promise that if there is a solution, then there is
one where all the variables are pairwise disjoint.

As in the proof of Theorem 2, we can construct the constant $0$ using a
constraint $x+y=x$, and thus, without loss of generality, by the distinctness
assumption, we can assume that there are exactly two variables in $X$ equal to
respectively $0$ or $1$, and that the others are different from $0$ and $1$.
By a slight abuse of language, we remove those from $X$ and denote them
directly by $0$ and $1$ in the rest of the description. We define a rank-$3$
matroid $M$ as follows. First, we have a line $\ell$ consisting of three
distinguished distinct points $0$, $1$ and $\infty$, as well as $n$ distinct
points (and distinct from $\\{0,1,\infty\\}$) corresponding to the variables
$\\{x_{1},\ldots x_{n}\\}$. We also add a line at infinity $\ell_{\infty}$
going through $\infty$ and no other point.

We then use the gadgets from Section 3 to inductively encode all the
constraints. Note that there is at most one constraint $x=1$ which can be
hardcoded from the start. Then let us assume inductively that we have defined
a matroid $M_{i}$ encoding the first $i$ constraints. The $i+1$th constraint
is an addition, a multiplication, or a strict inequality, which can be encoded
using a geometric construction as described in Section 3. Now, the key
property of these constructions is that the set of helper points is free.
Therefore, the only linear dependencies involved in the construction are those
of that construction, which can be readily encoded into a matroid $M_{i+1}$.

We now prove that the Distinct-ETR instance has a solution with distinct
variables if and only if the matroid $M$ is representable over the reals.
First, if Distinct-ETR has a solution, we obtain a representation of $M$ over
the reals by placing all the variables $x_{1},\ldots,x_{n}$ on the line $\ell$
at the values indicated by the solution, and by sending the line at infinity
to infinity. The geometric constructions are then represented one by one, and
since the helper points are free, by perturbing them if needed we can ensure
that they are all distinct, that no three of them are colinear, and that they
do not form colinearities with previously placed points. Therefore, this
constitutes a correct representation of the matroid. Conversely, given a
representation of the matroid $M$ over the reals, we read the values of the
variables on the line $\ell$ using cross-ratios as explained in Section 3 (or
equivalently we send $\ell_{\infty}$ to $\infty$ and use the oriented distance
to $0$). This gives us values for the variables of the Distinct-ETR instance.
The definition of the addition, multiplication and strict inequality
constructions ensures that each of the constraints will be satisfied.
Furthermore, by definition of the matroid, all of the variables are distinct.
This finishes the proof.

## References

  * [1] Mikkel Abrahamsen.  Covering Polygons is Even Harder.  In Nisheeth K. Vishnoi, editor, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 375–386, 2022.
  * [2] Mikkel Abrahamsen, Anna Adamaszek, and Tillmann Miltzow.  The Art Gallery Problem is $\exists\mathbb{R}$-complete.  In STOC 2018: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 65–73, 2018.
  * [3] Mikkel Abrahamsen, Linda Kleist, and Tillmann Miltzow.  Training Neural Networks is ER-complete.  In Marc A. Ranzato, Alina Beygelzimer, K. Nguyen, Percy Liang, Jennifer W. Vaughan, and Yann Dauphin, editors, Advances in Neural Information Processing Systems (NeurIPS 2021), volume 34, 2021.
  * [4] Mikkel Abrahamsen, Tillmann Miltzow, and Nadja Seiferth.  Framework for ER-Completeness of Two-Dimensional Packing Problems.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1014–1021, 2020.
  * [5] Saugata Basu and Marie-Fran$\mathbf{c}$coise Roy.  Bounding the radii of balls meeting every connected component of semi-algebraic sets.  Journal of Symbolic Computation, 45(12):1270–1279, 2010.
  * [6] Marie L. T. Berthelsen and Kristoffer A. Hansen.  On the Computational Complexity of Decision Problems About Multi-player Nash Equilibria.  In Dimitris Fotakis and Evangelos Markakis, editors, International Symposium on Algorithmic Game Theory, volume 11801 of Lecture Notes in Computer Science, pages 153–167, 2019.
  * [7] Daniel Bertschinger, Nicolas El Maalouly, Tillmann Miltzow, Patrick Schnider, and Simon Weber.  Topological art in simple galleries.  In Symposium on Simplicity in Algorithms (SOSA), pages 87–116. SIAM, 2022.
  * [8] Daniel Bertschinger, Christoph Hertrich, Paul Jungeblut, Tillmann Miltzow, and Simon Weber.  Training fully connected neural networks is $\exists\mathbb{R}$-complete.  arXiv preprint arXiv:2204.01368, 2022.
  * [9] Vittorio Bilò and Marios Mavronicolas.  A Catalog of EXISTS-R-Complete Decision Problems About Nash Equilibria in Multi-Player Games.  In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:13, 2016.
  * [10] Vittorio Bilò and Marios Mavronicolas.  Existential-R-Complete Decision Problems about Symmetric Nash Equilibria in Symmetric Multi-Player Games.  In Vollmer Heribert and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), volume 66 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1–13:14, 2017.
  * [11] Anders Björner, Michel Las Vergnas, Bernd Sturmfels, Neil White, and Gunter M Ziegler.  Oriented matroids.  Number 46. Cambridge University Press, 1999.
  * [12] Lenore Blum, Mike Shub, and Steve Smale.  On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines.  Bulletin of the American Mathematical Society, 21:1–46, 1989.
  * [13] Amanda Cameron.  Kinser inequalities and related matroids.  arXiv preprint arXiv:1401.0500, 2014.
  * [14] Amanda Cameron.  Polytopal and structural aspects of matroids and related objects.  PhD thesis, Queen Mary University of London, 2017.
  * [15] Amanda Cameron, Rodica Dinu, Mateusz Michałek, and Tim Seynnaeve.  Flag matroids: algebra and geometry.  In International Conference on Interactions with Lattice Polytopes, pages 73–114. Springer, 2022.
  * [16] Amanda Cameron and Dillon Mayhew.  Excluded minors for matroids satisfying kinser’s inequalities.  Graphs and Combinatorics, 32(1):31–47, 2016.
  * [17] Amanda Cameron and Dillon Mayhew.  Excluded minors for the class of split matroids.  arXiv preprint arXiv:1707.02239, 2017.
  * [18] John Canny.  Some Algebraic and Geometric Computations in PSPACE.  In STOC ’88: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pages 460–467, 1988.
  * [19] Jean Cardinal, Stefan Felsner, Tillmann Miltzow, Casey Tompkins, and Birgit Vogtenhuber.  Intersection Graphs of Rays and Grounded Segments.  Journal of Graph Algorithms and Applications, 22(2):273–294, 2018\.
  * [20] Dmitry Chistikov, Stefan Kiefer, Ines Marusic, Mahsa Shirmohammadi, and James Worrell.  On Restricted Nonnegative Matrix Factorization.  In Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi, editors, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 103:1–103:14, 2016\.
  * [21] Michael G. Dobbins, Andreas Holmsen, and Tillmann Miltzow.  A Universality Theorem for Nested Polytopes.  arXiv preprint, 2019.
  * [22] Michael G. Dobbins, Linda Kleist, Tillmann Miltzow, and Paweł Rzążewski.  $\forall\exists\mathbb{R}$-Completeness and Area-Universality.  In Andreas Brandstädt, Ekkehard Köhler, and Klaus Meer, editors, Graph-Theoretic Concepts in Computer Science (WG 2018), volume 11159 of Lecture Notes in Computer Science, pages 164–175. Springer, 2018\.
  * [23] Jeff Erickson.  Optimal Curve Straightening is $\exists\mathbb{R}$-Complete.  arXiv preprint, 2019.
  * [24] Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow.  Smoothing the gap between NP and ER.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1022–1033, 2020.
  * [25] Jugal Garg, Ruta Mehta, Vijay V. Vazirani, and Sadra Yazdanbod.  $\exists\mathbb{R}$-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria.  ACM Transactions on Economics and Computation, 6(1):1:1–1:23, 2018\.
  * [26] Jim Geelen and Geoff Whittle.  Certifying non-representability of matroids over prime fields.  J. Comb. Theory, Ser. B, 117:22–33, 2016.
  * [27] Heisuke Hironaka.  Triangulations of algebraic sets.  In Algebraic geometry (Proc. Sympos. Pure Math., Vol. 29, Humboldt State Univ., Arcata, Calif., 1974), volume 29, pages 165–185, 1975\.
  * [28] Petr Hlinený.  On matroid representability and minor problems.  In Rastislav Kralovic and Pawel Urzyczyn, editors, Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings, volume 4162 of Lecture Notes in Computer Science, pages 505–516. Springer, 2006.
  * [29] Per M. Jensen and Bernhard Korte.  Complexity of matroid property algorithms.  SIAM Journal on Computing, 11(1):184–190, 1982.
  * [30] Jisu Jeong, Eun Jung Kim, and Sang-il Oum.  Finding branch-decompositions of matroids, hypergraphs, and more.  SIAM J. Discret. Math., 35(4):2544–2617, 2021.
  * [31] Gabriela Jeronimo, Daniel Perrucci, and Elias Tsigaridas.  On the minimum of a polynomial function on a basic closed semialgebraic set and applications.  SIAM Journal on Optimization, 23(1):241–255, 2013.
  * [32] Bert Gerards Jim Geelen and Geoff Whittle.  Solving rota’s conjecture.  Notices of the American Mathematical Society, 61:736–743, 2014\.
  * [33] Paul Jungeblut, Linda Kleist, and Tillmann Miltzow.  The complexity of the hausdorff distance.  In Xavier Goaoc and Michael Kerber, editors, 38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany, volume 224 of LIPIcs, pages 48:1–48:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
  * [34] Ross Kang and Tobias Müller.  Sphere and Dot Product Representations of Graphs.  Discrete & Computational Geometry, 47(3):548–569, 2012.
  * [35] Donald E Knuth.  The asymptotic number of geometries.  Journal of Combinatorial Theory, Series A, 16(3):398–400, 1974\.
  * [36] Jan Kratochvíl and Jiří Matoušek.  Intersection Graphs of Segments.  Journal of Combinatorial Theory, Series B, 62(2):289–315, 1994\.
  * [37] Stefan Kratsch and Magnus Wahlström.  Representative sets and irrelevant vertices: New tools for kernelization.  J. ACM, 67(3):16:1–16:50, 2020.
  * [38] Laurent Lafforgue.  Chirurgie des grassmanniennes.  Number 19. American Mathematical Soc., 2003.
  * [39] Seok Hyeong Lee and Ravi Vakil.  Mnëv-sturmfels universality for schemes.  A celebration of algebraic geometry, 18:457–468, 2013.
  * [40] László Lovász.  Matroid matching and some applications.  J. Comb. Theory, Ser. B, 28(2):208–236, 1980.
  * [41] Anna Lubiw, Tillmann Miltzow, and Debajyoti Mondal.  The Complexity of Drawing a Graph in a Polygonal Region.  In Therese Biedl and Andreas Kerren, editors, GD 2018: Graph Drawing and Network Visualization, volume 11282 of Lecture Notes in Computer Science, pages 387–401, 2018.
  * [42] Lovász László.  Flats in matroids and geometric graphs.  Combinatorial Surveys, 01 1977.
  * [43] Dániel Marx.  A parameterized view on matroid optimization problems.  Theor. Comput. Sci., 410(44):4471–4479, 2009.
  * [44] Jiří Matoušek.  Intersection graphs of segments and $\exists\mathbb{R}$.  arXiv preprint, 2014.
  * [45] Dillon Mayhew.  Matroid complexity and nonsuccinct descriptions.  SIAM J. Discret. Math., 22(2):455–466, 2008.
  * [46] Colin McDiarmid and Tobias Müller.  Integer realizations of disk and segment graphs.  Journal of Combinatorial Theory, Series B, 103(1):114–143, 2013\.
  * [47] Tillmann Miltzow and Reinier F. Schmiermann.  On Classifying Continuous Constraint Satisfaction Problems.  In Nisheeth K. Vishnoi, editor, 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 781–791, 2022.
  * [48] Nikolai E. Mnëv.  The Universality Theorems on the Classification Problem of Configuration Varieties and Convex Polytopes Varieties.  In Oleg Y. Viro and Anatoly M Vershik, editors, Topology and Geometry — Rohlin Seminar, volume 1346 of Lecture Notes in Mathematics, pages 527–543. Springer, 1988.
  * [49] Sang-il Oum and Paul D. Seymour.  Testing branch-width.  J. Comb. Theory, Ser. B, 97(3):385–393, 2007.
  * [50] James G Oxley.  Matroid theory, volume 3.  Oxford University Press, USA, 2006.
  * [51] Jürgen Richter-Gebert and Günter M. Ziegler.  Realization Spaces of 4-Polytopes are Universal.  Bulletin of the American Mathematical Society, 32(4):403–412, 1995\.
  * [52] Marcus Schaefer.  Complexity of Some Geometric and Topological Problems.  In David Eppstein and Emden R. Gansner, editors, GD 2009: Graph Drawing, volume 5849 of Lecture Notes in Computer Science, pages 334–344, 2010.
  * [53] Marcus Schaefer.  Realizability of Graphs and Linkages, pages 461–482.  Thirty Essays on Geometric Graph Theory. Springer, 2013.
  * [54] Marcus Schaefer.  Complexity of Geometric k-Planarity for Fixed k.  Journal of Graph Algorithms and Applications, 25(1):29–41, 2021\.
  * [55] Marcus Schaefer and Daniel Štefankovič.  Fixed Points, Nash Equilibria, and the Existential Theory of the Reals.  Theory of Computing Systems, 60:172–193, 2017.
  * [56] Marcus Schaefer and Daniel Štefankovič.  The Complexity of Tensor Rank.  Theory of Computing Systems, 62(5):1161–1174, 2018.
  * [57] Yaroslav Shitov.  A Universality Theorem for Nonnegative Matrix Factorizations.  arXiv preprint, 2016.
  * [58] Yaroslav Shitov.  The complexity of positive semidefinite matrix factorization.  SIAM Journal on Optimization, 27(3):1898–1909, 2017.
  * [59] Peter W. Shor.  Stretchability of Pseudolines is NP-Hard.  In Peter Gritzmann and Bernd Sturmfels, editors, Applied Geometry And Discrete Mathematics, volume 4 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 531–554, 1991.
  * [60] K. Truemper.  On the efficiency of representability tests for matroids.  European Journal of Combinatorics, 3(3):275–291, 1982.
  * [61] Levent Tuncel, Stephen Vavasis, and Jingye Xu.  Computational complexity of decomposing a symmetric matrix as a sum of positive semidefinite and diagonal matrices.  arXiv preprint arXiv:2209.05678, 2022.