Approximating the existential theory of the reals

Deligkas, Argyrios, Fearnley, John, Melissourgos, Themistoklis and Spirakis, Paul G ORCID: 0000-0001-5396-3749 (2022) Approximating the existential theory of the reals. Journal of Computer and System Sciences, 125. pp. 106-128.

Text
rev_2.pdf - Author Accepted Manuscript
Download (619kB) | Preview

Official URL: http://dx.doi.org/10.1016/j.jcss.2021.11.002

Abstract

The Existential Theory of the Reals (ETR) consists of existentially quantified Boolean formulas over equalities and inequalities of polynomial functions of real variables. In this paper we propose and study the approximate existential theory of the reals (ϵ-ETR) in which the constraints are only satisfied approximately. We first show that when the domain of the variables is the reals then ϵ-ETR = ETR under polynomial time reductions, and then study the constrained ϵ-ETR problem where groups of variables are constrained to lie in bounded convex sets. Our main result is a sampling theorem that discretizes the domain in a grid-like manner whose density depends on various properties of the ETR formula. A consequence of our theorem is that we obtain a (quasi-)polynomial time approximation scheme ((Q)PTAS) for a fragment of constrained ϵ-ETR. We use this theorem to create several new PTAS and QPTAS for problems from a variety of fields.

Item Type:	Article
Uncontrolled Keywords:	Approximation schemes, Existential theory of the reals, Function problems
Divisions:	Faculty of Science and Engineering > School of Electrical Engineering, Electronics and Computer Science
Depositing User:	Symplectic Admin
Date Deposited:	14 Dec 2021 10:27
Last Modified:	18 Jan 2023 21:19
DOI:	10.1016/j.jcss.2021.11.002
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3145347