A survey of quantitative bounds on the complexity of definable sets

Saugata Basu
Purdue University

I will survey the known results on bounding the topological
complexities of semi-algebraic as well as more general definable sets. Starting from the
first results in this direction due to Oleinik and Petrovskii, some of these results have
been used in several different ways in discrete and computational geometry as well as in other areas
of mathematics an computer science.
I will state what is known, give hints on how the results are proved, and mention some open questions.


Back to Long Programs