讨论组:算法、复杂性及密码组
标题:Random polynomials and expected complexity of real solving
演讲人: Elias Tsigaridas University
时间: 2011-10-26 15:30-2011-10-26 16:15
地点: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.