# Approximating the Existential Theory of the Reals

@article{Deligkas2018ApproximatingTE, title={Approximating the Existential Theory of the Reals}, author={Argyrios Deligkas and John Fearnley and Themistoklis Melissourgos and Paul G. Spirakis}, journal={ArXiv}, year={2018}, volume={abs/1810.01393} }

The existential theory of the reals (ETR) consists of existentially quantified boolean formulas over equalities and inequalities of real-valued polynomials. We propose the approximate existential theory of the reals (\(\epsilon \)-ETR), in which the constraints only need to be satisfied approximately. We first show that unconstrained \(\epsilon \)-ETR = ETR, and then study the \(\epsilon \)-ETR problem when the solution is constrained to lie in a given convex set. Our main theorem is a sampling… Expand

#### Topics from this paper

#### 3 Citations

Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

- Computer Science, Mathematics
- ICALP
- 2019

A new complexity class BU is defined, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly, and it is shown that FIXP $\subseteq$ BU $\sub seteq$ TFETR and that LinearBU $=$ PPA, where LinearBU is the subclass of BU in which the BORSuk- Ulam instance is specified by a linear arithmetic circuit. Expand

Lipschitz Continuity and Approximate Equilibria

- Mathematics, Computer Science
- Algorithmica
- 2020

The key insight is that Lipschitz continuity of the payoff function allows us to provide algorithms for finding approximate equilibria in games with continuous action spaces and non-linear payoff functions. Expand

Algorithms and complexity of problems arising from strategic settings

- Computer Science
- 2019

This thesis deals with an evolutionary setting where it is shown that for a wide range of symmetric bimatrix games, deciding ESS existence is intractable, and presents a general framework for constructing approximation schemes for problems that can be written as an Existential Theory of the Reals formula with variables constrained in a bounded convex set. Expand

#### References

SHOWING 1-10 OF 40 REFERENCES

Fixed Points, Nash Equilibria, and the Existential Theory of the Reals

- Computer Science, Mathematics
- Theory of Computing Systems
- 2015

It is shown that the complexity of decision variants of fixed-point problems, including Nash equilibria, are complete for this class, complementing work by Etessami and Yannakakis. Expand

On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines

- Mathematics
- 1989

We present a model for computation over the reals or an arbitrary (ordered) ring R. In this general setting, we obtain universal machines, partial recursive functions, as well as JVP-complete… Expand

Computing Exact Solutions of Consensus Halving and the Borsuk-Ulam Theorem

- Computer Science, Mathematics
- ICALP
- 2019

A new complexity class BU is defined, which captures all problems that can be reduced to solving an instance of the Borsuk-Ulam problem exactly, and it is shown that FIXP $\subseteq$ BU $\sub seteq$ TFETR and that LinearBU $=$ PPA, where LinearBU is the subclass of BU in which the BORSuk- Ulam instance is specified by a linear arithmetic circuit. Expand

Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory's Theorem

- Mathematics, Computer Science
- STOC
- 2015

This paper establishes that in a bimatrix game with n x n payoff matrices A, B, if the number of non-zero entries in any column of A+B is at most s then an ε-Nash equilibrium of the game can be computed in time nO(log s/ε2}). Expand

On oblivious PTAS's for nash equilibrium

- Mathematics, Computer Science
- STOC '09
- 2009

It is proved that any oblivious PTAS for anonymous games with two strategies and three player types must have 1/εα in the exponent of the running time for some α ≥ 1/3, rendering the algorithm in [Daskalakis 2008] (which works with any bounded number of player types) essentially optimal within oblivious algorithms. Expand

A PTAS for the minimization of polynomials of fixed degree over the simplex

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2006

It is shown that the bounds pΔ(k) yield a polynomial time approximation scheme for the minimization of polynomials of fixed degree d on the simplex, extending an earlier result of Bomze and De Klerk for degree d = 2. Expand

Some algebraic and geometric computations in PSPACE

- Mathematics, Computer Science
- STOC '88
- 1988

A PSPACE algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations is given and it is shown that the existential theory of the real numbers can be decided in PSPACE. Expand

Inapproximability results for constrained approximate Nash equilibria

- Mathematics, Computer Science
- Inf. Comput.
- 2018

The main result is that, if the exponential-time hypothesis (ETH) is true, then solving ( 1 8 − O ( δ ) -NE O (δ) -SW for an n × n bimatrix game requires n Ω ˜ ( log n ) time. Expand

∃R-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria

- Computer Science, Mathematics
- ACM Trans. Economics and Comput.
- 2018

This work shows that checking whether a three-player Nash Equilibrium (3-Nash) instance has an equilibrium in a ball of radius half in l∞-norm is ∃R-complete, where ∃ R is the class of decision problems that can be reduced in polynomial time to Existential Theory of the Reals. Expand

Inapproximability of NP-Complete Variants of Nash Equilibrium

- Mathematics, Computer Science
- APPROX-RANDOM
- 2011

It is shown that optimal Nash equilibrium is just one of several known NP-hard problems related to Nash equilibrium, all of which have approximate variants which are as hard as finding a planted clique, and for general Bayesian games the problem is NP- hard. Expand