  The Existential Theory of the Reals (ETR) consists of existentially
quantified Boolean formulas over equalities and inequalities of polynomial
functions of variables in $\mathbb{R}$. In this paper we propose and study the
approximate existential theory of the reals ($\epsilon$-ETR), in which the
constraints only need to be satisfied approximately. We first show that when
the domain of the variables is $\mathbb{R}$ then $\epsilon$-ETR = ETR under
polynomial time reductions, and then study the constrained $\epsilon$-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 $\epsilon$-ETR. We
use our theorem to create several new PTAS and QPTAS algorithms for problems
from a variety of fields.
