## COUNTING ROOTS OF POLYNOMIAL SYSTEMS (over the real numbers)

One surprisingly overlooked aspect of random polynomial
systems is how ``sparsity'' effects the expected number of
real roots. That is, how does the monomial term structure
effect stochastic real root counting? A first step towards
an answer appears in
``On the Average Number of Real Roots of Certain Sparse Polynomial
Systems'' (to appear in the upcoming Lectures in Applied
Mathematics Series volume edited by Jim Renegar, Mike Shub,
and Steve Smale, American Mathematical Society, 1996). There,
a natural probability measure is proposed for certain spaces
of sparse polynomial systems, and the Square Root Volume Conjecture
(verified in a few important cases) gives a bold guess as to how things go
in this setting.
A later paper describes how toric resultants can
be combined with Sturm sequences to quickly count the exact number of
real roots of a system of polynomial equations. Explicit
complexity bounds (the best known in a broad family of cases) are given as well.
``Intrinsic Near Quadratic Complexity Bounds for
Real Multivariate Root Counting.'' is now on-line.

More recently, I have found a nice improvement to older
bounds of Basu, Milnor, Oleinik, Petrovsky, and Thom on the
number of connected components of a semi-algebraic set.
(Semi-algebraic sets are the solution sets of general
polynomial inequalities over the real numbers.)
The relevant paper, which won the Journal of Complexity 2000
Best Paper Award, is ``Some Speed-Ups and Speed-Limits in
Real Algebraic Geometry,'' and can be found on my papers page.

My latest work deals with turning these sharper quantitative
bounds into faster algorithms. In particular, can fewnomial theory
be made fully algorithmic in an intrinsic way?