Videos

A Critical Radius for Low Complexity

Presenter
April 20, 2007
Keywords:
  • Discriminantal varieties
MSC:
  • 55R80
Abstract
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.