Group:Algorithms, Complexity and Cryptography Group
Title: Random polynomials and expected complexity of real solving
Speaker: Elias Tsigaridas University
Time: 2011-10-26 15:30-2011-10-26 16:15
Venue: FIT 1-222


We present results that shed light to the following questions: Why do random polynomials seem to have few and well separated real roots, on the average? Why do exact algorithms for real solving of univariate polynomials may perform comparatively well or even better than numerical ones?

We study degree-d polynomials with iid coefficients under two zero-mean normal distributions, such that the i-th coefficient has variance (d \choose i), or 1/i!. For Bernstein polynomials with iid coefficients of moderate standard deviation, we show that the expected number of real roots is \sqrt{d} \pm O(1).

Joint work with Ioannis Emiris and Andre Galligo.