Given polynomials g and f1, …, fp, all in <Formula format="inline"><TexMath><?TeX $\field [x_1,\dots,x_n]$?></TexMath><AltText>Math 1</AltText><File name="issac24-43-inline1" type="svg"/></Formula> for some field <Formula format="inline"><TexMath><?TeX $...

Separation bounds are a fundamental measure of the complexity of solving a zero-dimensional system as it measures how difficult it is to separate its zeroes. In the positive dimensional case, the notion of reach takes its place. In this paper, we ...

Consider a system f1(x) = 0, …, fn(x) = 0 of n random real polynomials in n variables, where each fi has a prescribed set of exponent vectors in a set of cardinality ti, whose convex hull is denoted Pi. Assuming that the coefficients of the fi are ...

We consider the problem of answering connectivity queries on a real algebraic curve. The curve is given as the real trace of an algebraic curve, assumed to be in generic position, and being defined by some rational parametrizations. The query points are ...

Pourchet proved in 1971 that every nonnegative univariate polynomial with rational coefficients is a sum of five or fewer squares. Nonetheless, there are no known algorithms for constructing such a decomposition. The sole purpose of the present paper is ...

We present a full analysis of the bit complexity of an efficient algorithm for the computation of at least one point in each connected component of a smooth real hypersurface. This is a basic and important operation in semi-algebraic geometry: it gives ...

Let R be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in Rⁿ given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of ...

We provide two hybrid numeric-symbolic optimization algorithms, computing exact sums of nonnegative circuits (SONC) and sums of arithmetic-geometric-exponentials (SAGE) decompositions. Moreover, we provide a hybrid numeric-symbolic decision algorithm for ...

Let f= (f₁, ..., f_s) be a sequence of polynomials in Q[X₁,...,X_n] of maximal degree D and V⊂ Cⁿ be the algebraic set defined by f and r be its dimension. The real radical re < f > associated to f is the largest ideal which defines the real trace of V . ...

We consider the problem of finding exact sums of squares (SOS) decompositions for certain classes of non-negative multivariate polynomials, relying on semidefinite programming (SDP) solvers. We start by providing a hybrid numeric-symbolic algorithm ...

The intersection of a quadric and a cubic surface in 3-space is a canonical curve of genus 4. It has 120 complex tritangent planes. We present algorithms for computing real tritangents, and we study the associated discriminants. We focus on space ...

This article introduces differential hybrid games, which combine differential games with hybrid games. In both kinds of games, two players interact with continuous dynamics. The difference is that hybrid games also provide all the features of hybrid ...

A roadmap for a semi-algebraic set S is a curve which has a non-empty and connected intersection with all connected components of S. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with applications, for ...

Signomial programs (SPs) are optimization problems specified in terms of signomials, which are weighted sums of exponentials composed with linear functionals of a decision variable. SPs are nonconvex optimization problems in general, and families of NP-...

In this paper we extend complex homotopy methods to finding witness points on the irreducible components of real varieties. In particular we construct such witness points as the isolated real solutions of a constrained optimization problem.

First a ...

Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly ...

We show that every real nonnegative polynomial $f$ can be approximated as closely as desired (in the $l_1$-norm of its coefficient vector) by a sequence of polynomials $\{f_\epsilon\}$ that are sums of squares. The novelty is that each $f_\epsilon$ has ...

The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints (FO+poly). For reasons of ...

We consider a polynomial programming problem $\P$ on a compact basic semialgebraic set $\K\subset\R^n$, described by $m$ polynomial inequalities $g_j(X)\geq0$, and with criterion $f\in\R[X]$. We propose a hierarchy of semidefinite relaxations in the ...