A Critical Radius for Low Complexity <br/><br/><br/><br/>

Friday, April 20, 2007 - 1:30pm - 2:20pm
EE/CS 3-180
J. Maurice Rojas (Texas A & M University)
Just as the number of real roots of a real univariate quadratic
depends on the sign of the discriminant, the topological behavior of real
zero sets depends on (more general) A-discriminant variety complements.
More recently, in numerical linear algebra (and nonlinear work of Shub, Smale,
Beltran, Pardo, and other authors), the relationship between the numerical
behavior of zero sets and distance to the discriminant variety has been

In this talk, we review some of the connections between
A-discriminants, the topology of real algebraic sets, and the
complexity of solving polynomial systems. In particular, we show
that outside a ball of sufficiently large radius (in the coefficient space),
one can assert the following with high probability:

(1) a new upper bound on the number of real roots of a fewnomial
system, significantly improving Khovanski's famous result

(2) the truth of a formerly broken conjecture of Itenberg and

Our main results are joint work in progress with Martin Avendano.
We also discuss a connection to a generalization of Smale's 17th Problem.
No background in algebraic geometry is assumed.
MSC Code: