Fast interpolation and multiplication of unbalanced polynomials
<|reference_start|>Fast interpolation and multiplication of unbalanced polynomials: We consider the classical problems of interpolating a polynomial given a black box for evaluation, and of multiplying two polynomials, in the setting where the bit-lengths of the coefficients may vary widely, so-called unbalanced polynomials. Writing s for the total bit-length and D for the degree, our new algorithms have expected running time $\tilde{O}(s \log D)$, whereas previous methods for (resp.) dense or sparse arithmetic have at least $\tilde{O}(sD)$ or $\tilde{O}(s^2)$ bit complexity.<|reference_end|>
@article{giorgi2024fast,
    title={Fast interpolation and multiplication of unbalanced polynomials},
    author={Pascal Giorgi and Bruno Grenet and Armelle Perret du Cray and Daniel
  S. Roche},
    journal={ISSAC '24: Proceedings of the 2024 International Symposium on
  Symbolic and Algebraic Computation, pp. 437--446},
    year={2024},
    doi={10.1145/3666000.3669717},
    archivePrefix={arXiv},
    eprint={2402.10139},
    primaryClass={cs.SC cs.CC}
}