### DIMACS Theoretical Computer Science Seminar

Title:
Efficient Algorithms for Computing the Betti Numbers of Semi-algebraic Sets

Speaker: **Saugata Basu**, Georgia Tech

Date: October 11, 2005 2:00-3:00pm

Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ

Abstract:

Computing homological information of semi-algebraic sets (or more generally
constructible sets) is an important problem for several reasons. From
the point of view of computational complexity theory, it is the next
logical step after the problem of deciding emptiness of such sets, which
is the signature NP-complete problem in appropriate models of computation.

In this talk I will describe some recent progress in designing efficient
algorithms for computing the Betti numbers of semi-algebraic sets in
several different settings. I will describe a single exponential time
algorithm for computing the first few Betti numbers in the general case
and polynomial time algorithms in case the set is defined in terms of
quadratic inequalities. One common theme underlying these algorithms is
the use of certain spectral sequences -- namely, the Mayer-Vietoris spectral
sequence and the ``cohomological descent'' spectral sequence first introduced
by Deligne.

Certain parts of this work is joint with R. Pollack, M-F. Roy
and (separately) with T. Zell.