🚀 go-pugleaf

           Department of Computer Science, University of Toronto
         (SF = Sandford Fleming Building, 10 King's College Road)

       -------------------------------------------------------------

                                  THEORY
                   SF1105, at 3:00 p.m., 3 December 1992

                             Nicolai Vorobjov
                                MSI Cornell

                         "COMPLEXITY OF COMPUTING
              TOPOLOGICAL PROPERTIES OF A SEMIALGEBRAIC SET"

In the last few years, some new effective algorithms have been developed
for basic computational problems in real algebraic geometry. The complexity
of the algorithms is singly-exponential in the number of variables, in
contrast to thepreviously known doubly-exponential upper time bounds. A
survey of these methods will be given with a more detailed description of
the most advanced of them: an algorithm for finding all connected
components of a semialgebraic set and a procedure for computing the
combinatorial type of a cell-decomposition of a smooth real algebraic
hypersurface.