9402640 Pollack This project is devoted to improving algorithms for the existential theory of the reals, the general decision problem for real closed fields and quantifier elimination over real closed fields. The goal is to be able to separate the complexity of these algorithms into a combinatorial part (the dependence on the number of input polynomials) and an algebraic part (the dependence on the degrees of these polynomials). The project should produce algorithms which are combinatorially optimal. One step in such algorithms is to compute a set of points which meet every cell determined by a family of polynomials. The project will extend this task, and will compute a set of points on a variety of real dimension k which meets every cell of a family of polynomials in such a way that the combinatorial complexity depends optimally on k. ***
