# Approximating the Existential Theory of the Reals

arXiv: https://arxiv.org/abs/1810.01393 · HTML: https://mlsanity.com/paper/1810.01393/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Oct 2018.

## Built on by (most cited first, 2 of 2)

- [Training Fully Connected Neural Networks is existsℝ-Complete](https://mlsanity.com/paper/2204.01368/) (2022)
- [On Classifying Continuous Constraint Satisfaction Problems](https://mlsanity.com/paper/2106.02397/) (2021)

## Abstract (arXiv)

The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of variables in ℝ. In this paper we propose and study the approximate existential theory of the reals (ε-ETR), in which the constraints only need to be satisfied approximately. We first show that when the domain of the variables is ℝ then ε-ETR = ETR under polynomial time reductions, and then study the constrained ε-ETR problem when the variables are constrained to lie in a given bounded convex set. Our main theorem is a sampling theorem, similar to those that have been proved for approximate equilibria in normal form games. It discretizes the domain in a grid-like manner whose density depends on various properties of the formula. A consequence of our theorem is that we obtain a quasi-polynomial time approximation scheme (QPTAS) for a fragment of constrained ε-ETR. We use our theorem to create several new PTAS and QPTAS algorithms for problems from a variety of fields.