A quasi-optimal lower bound for skew polynomial multiplication

Qiyuan Chen, Ke Ye

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…