English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The Existential Theory of the Reals (ETR) consists of existentiallyquantified Boolean formulas over equalities and inequalities of polynomialfunctions of variables in $\mathbb{R}$. In this paper we propose and study theapproximate existential theory of the reals ($\epsilon$-ETR), in which theconstraints only need to be satisfied approximately. We first show that whenthe domain of the variables is $\mathbb{R}$ then $\epsilon$-ETR = ETR underpolynomial time reductions, and then study the constrained $\epsilon$-ETRproblem when the variables are constrained to lie in a given bounded convexset. Our main theorem is a sampling theorem, similar to those that have beenproved for approximate equilibria in normal form games. It discretizes thedomain in a grid-like manner whose density depends on various properties of theformula. A consequence of our theorem is that we obtain a quasi-polynomial timeapproximation scheme (QPTAS) for a fragment of constrained $\epsilon$-ETR. Weuse our theorem to create several new PTAS and QPTAS algorithms for problemsfrom a variety of fields.

Approximating the Existential Theory of the Reals