2024/02/06 by Qiyuan Chen, Ke Ye, Chen, Qiyuan +1
Computer Science · Engineering · #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Polynomial and algebraic computation #Rings and Algebras (math.RA) #Symbolic Computation (cs.SC) #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2402.04134
openalex publication_date 2024/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We establish a lower bound for the complexity of multiplying two skew polynomials. The lower bound coincides with the upper bound conjectured by Caruso and Borgne in 2017, up to a log factor. We present algorithms for three special cases, indicating that the aforementioned lower bound is quasi-optimal. In fact, our lower bound is quasi-optimal in the sense of bilinear complexity. In addition, we discuss the average bilinear complexity of simultaneous multiplication of skew polynomials and the complexity of skew polynomial multiplication in the case of towers of extensions.