A new paper by Alperen Ergür, @Elias Tsigaridas and Josué Tonelli-Cuerto (https://arxiv.org/abs/2202.06428). 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.
- IMJ-PRG Institut de Mathématiques de Jussieu – Paris rive gauche.
- INRIA Paris INRIA Paris research center