Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Alexey Pospelov:

TR10-152 | 6th October 2010
Alexey Pospelov

Faster Polynomial Multiplication via Discrete Fourier Transforms

We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different ... more >>>

TR10-049 | 24th March 2010
Alexey Pospelov

Bounds for Bilinear Complexity of Noncommutative Group Algebras

Revisions: 1 , Comments: 1

We study the complexity of multiplication in noncommutative group algebras which is closely related to the complexity of matrix multiplication. We characterize such semisimple group algebras of the minimal bilinear complexity and show nontrivial lower bounds for the rest of the group algebras. These lower bounds are built on the ... more >>>

ISSN 1433-8092 | Imprint