|
|
|
|
|
|
|
|
Efficient Algorithms for Computing the Betti Numbers of Semi-algebraic Sets
In this talk I will describe some new algorithms for computing the Betti numbers of semi-algebraic sets. More precisely, I will describe an algorithm for computing the first few Betti numbers of any given semi-algebraic set whose complexity is singly exponential in the dimension. Previously, only the zero-th Betti number was known to be computable in single exponential time. I will also describe a polynomial time algorithm for computing certain Betti numbers of sets defined by quadratic inequalities.
Thursday, September 16, 2004, 245 Altgeld Hall, 4 p.m.
Mathematics Colloquia homepage