  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.
