An Introduction to Algorithms in Real Algebraic Geometry

---

Instructor : Richard Pollack
New York University
Courant Institute of Mathematical Sciences
Department of Mathematics

Syllabus :

Lecture 1 (each lecture lasts 2 hours)
Real closed fields, Puiseux series, basic notions of semi-algebraic sets.

Lecture 2
Naive real root counting and the Tarski-Seidenberg Principle (quantifier elimination over real closed fields).

Lecture 3
Multivariate algebra, practical polynomial system solving, efficient real root counting and sign determinations. (This lecture may be given by Prof. M.-F. Roy.)

Lecture 4
The geometry of semi-algebraic sets.

Lecture 5
The "existential theory of the reals", deciding whether or not a system of polynomial equalities and inequalities in many variables has a real solution.

Lecture 6
A birds eye view of;

(1) Fast quantifier elimination over real closed fields,
(2) Efficient construction of roadmaps of semi-algebraic sets,
(3) The existential theory of the reals and roadmaps on a variety of lower dimension.

References.

1. "Geometrie Algebrique Reele" by J. Bochnak, M. Coste and M.-F. Roy, Springer Verlag (1987)

2. "Basic algorithms in real algebraic geometry: from Sturm theorem to the existential theory of reals", M.-F. Roy, in Lectures on Real Geometry in memoriam of Mario Raimondo, de Gruyter Expositions in Mathematics, to appear.

3. "Algorithms in Real Algebraic Geometry" by S. Basu, R. Pollack and M.-F. Roy, (a work in progress, chapter preprints will be supplied)