A new paper by Alperen Ergür, @Elias Tsigaridas and Josué Tonelli-Cuerto ( They prove that the Descartes solver is optimal—O(d𝜏+d²)—in average for random bit polynomials, i.e., polynomials whose coefficients are random integers. Moreover, our method does not only apply just to the case where coefficients are uniformly chosen in a range, but it allows for a robust choice of the parameters.

Comments are closed.