# 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

clarified.

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

Roy

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.

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

clarified.

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

Roy

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:

55R80

Keywords: