@article{Hoeven:2021ab,
    Abstract = {We present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. We achieve a nearly quadratic running time in the number of solutions, for densely represented input polynomials. We also prove a nearly linear bit complexity bound for polynomial systems with rational coefficients. Our results are obtained using the combination of the Kronecker solver and a new improved algorithm for fast multivariate modular composition.},
    Author = {van der Hoeven, Joris and Lecerf, Gr{\'e}goire},
    Date = {2021/02/01},
    File = {On the Complexity Exponent of Polynomial System Solving - 10.1007@s10208-020-09453-0 - a.pdf},
    ISBN = {1615-3383},
    Journal = {Foundations of Computational Mathematics},
    Number = {1},
    Pages = {1--57},
    Title = {On the Complexity Exponent of Polynomial System Solving},
    URL = {https://doi.org/10.1007/s10208-020-09453-0},
    Volume = {21},
    Year = {2021},
    bdsk-url-1 = {https://doi.org/10.1007/s10208-020-09453-0},
    date-added = {2023-02-02 07:45:01 +0100},
    date-modified = {2023-02-02 07:45:01 +0100},
    id = {van der Hoeven2021},
    doi = {10.1007/s10208-020-09453-0}
}

@article{Hoeven:2021ab, Abstract = {We present a probabilistic Las Vegas algorithm for solving sufficiently generic square polynomial systems over finite fields. We achieve a nearly quadratic running time in the number of solutions, for densely represented input polynomials. We also prove a nearly linear bit complexity bound for polynomial systems with rational coefficients. Our results are obtained using the combination of the Kronecker solver and a new improved algorithm for fast multivariate modular composition.}, Author = {van der Hoeven, Joris and Lecerf, Gr{\'e}goire}, Date = {2021/02/01}, File = {On the Complexity Exponent of Polynomial System Solving - 10.1007@s10208-020-09453-0 - a.pdf}, ISBN = {1615-3383}, Journal = {Foundations of Computational Mathematics}, Number = {1}, Pages = {1--57}, Title = {On the Complexity Exponent of Polynomial System Solving}, URL = {https://doi.org/10.1007/s10208-020-09453-0}, Volume = {21}, Year = {2021}, bdsk-url-1 = {https://doi.org/10.1007/s10208-020-09453-0}, date-added = {2023-02-02 07:45:01 +0100}, date-modified = {2023-02-02 07:45:01 +0100}, id = {van der Hoeven2021}, doi = {10.1007/s10208-020-09453-0} }