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.