Algorithms in Real Algebraic Geometry: Recent Advances

Richard Pollack (Courant Institute)

We shall describe the problems known as the "Existential Theory of the Reals", the "General Decision problem for the reals" which are both special cases of "Quantifier Elimination over real closed fields" and the construction of "Roadmaps" for semi-algebraic sets. There is a long history of algorithmic solutions to these problems going back sixty years to Tarski followed by work of Collins, Schwartz-Sharir, Grigor'ev-Vorobjov, Heintz- Roy-Solerno, Canny and Renegar among others. Then we shall indicate some of the new ideas developed by Basu-Pollack-Roy that permit further improvements in these algorithms.