A quasi-optimal lower bound for skew polynomial multiplication
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911772158459904 |
|---|---|
| author | Chen, Qiyuan Ye, Ke |
| author_facet | Chen, Qiyuan Ye, Ke |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_04134 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A quasi-optimal lower bound for skew polynomial multiplication Chen, Qiyuan Ye, Ke Computational Complexity Symbolic Computation Rings and Algebras 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. |
| title | A quasi-optimal lower bound for skew polynomial multiplication |
| topic | Computational Complexity Symbolic Computation Rings and Algebras |
| url | https://arxiv.org/abs/2402.04134 |