Approximating the Existential Theory of the Reals

Abstract

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.

In the proceedings of the 14th Conference on Web and Internet Economics (WINE 2018)