A theorem on random polynomials and some consequences in average complexity (Q2277521)

The authors use results on the average number of real roots of real polynomials to get estimates for the average run time to compute different codings of the real algebraic numbers. These average run times are computed for polynomials in \(\mathbb Z[X]\), whose coefficients have a uniform distribution on an interval \([-d,d] \) for some \(d=2^ n\in\mathbb Z\).