Quasi-linear Time Multiplication of Sparse Polynomials with Integer Coefficients
This work addresses a fundamental open problem in computer algebra, offering efficient multiplication algorithms for sparse polynomials with integer or finite field coefficients.
The paper provides a counterexample to a previously claimed solution for quasi-linear time sparse polynomial multiplication with integer coefficients, and presents a new algorithm achieving quasi-linear bit complexity for integer coefficients and linear bit complexity for coefficients over finite fields.
Sparse polynomial multiplication is a fundamental problem in computer algebra and the theory of computation, and the development of a quasi-linear time output-sensitive multiplication algorithm has been posed as an open challenge. In this paper, a counterexample is provided to a previously claimed solution to this open problem for integer coefficients. By employing the existing quasi-linear modular-black-box interpolation algorithm, we are able to provide an algorithm with quasi-linear bit complexity for the integer coefficients setting. Furthermore, in the case of coefficients over a finite field, we obtain an algorithm whose bit complexity is linear in the number of terms, the logarithm of the degree, and the logarithm of the size of the finite field.