Using infinitesimals for algorithms in real algebraic geometry

Marie-Francoise Roy
Université de Rennes I

The critical point method is the basis of many recent algorithms in real algebraic geometry with quasi-optimal singly exponential complexity such that the existential theory of the reals, quantifier elimination (when the number of block of quantifiers is fixed) and deciding connectivity. Using it requires general position situations that are reached through various deformation tricks. In the algorithms, the notion of "small enough" is implemented through the use of infinitesimals. This talked is based on several papers written with S. Basu and/or R. Pollack.

Presentation (PDF File)

Back to Workshop II: Tools from Algebraic Geometry