Dima Pasechnik: Semialgebraic sets over quadratic maps

Abstract: A semialgebraic set S over a quadratic map Q is defined by a formula of the form F ( Q ( X )), for Q : Rⁿ -> R^k a quadratic map and F ( Y₁,..., Y₁ ) a first order formula over R. It turns out that the usual for n-variate semialgebraic sets quantity ( d s )^{O( n )}, for s the number of polynomial atoms f_j and d  their maximal degree, appearing in bounds (e.g. on Betti numbers) and algorithmic complexity estimates (e.g. for checking non-emptiness) for this class of sets can be often replaced by ( d n s )^{O( k )}. That is, such sets are "easy" for fixed k.

Specifically, we will discuss how one can find representatives of the connected components of S in ( d n s )^{O( k )} arithmetic operations in the ring generated by the coefficients of Q and f_j .

Time allowing, we will also address the question of estimating Betti numbers of S. In particular, we will show the bound d ( 2 d n + 2 )^{2 k} on the number of connected components of S in the aglebraic case, i.e. when s = 1 and F ( Y ) = ( f ( Y ) = 0).

References.

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in Real Algebraic Geometry. Springer, 2003.

D. Grigoriev, D. Pasechnik. Polynomial-time computing over quadratic maps I. Sampling in real algebraic sets. Computational Complexity 14(2005) 20-52 (e-print cs.SC/0403008 at arXiv.org)