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?