3 papers
math.GR2025
Finding cycle types in permutation groups with few generators
Markus Lohrey, Andreas Rosowski
The problem whether a given permutation group contains a permutation with a given cycle type is studied. This problem is known to be NP-complete. In this paper it is shown that the…
cs.DS2021
On Fast Computation of a Circulant Matrix-Vector Product
Andreas Rosowski
This paper deals with circulant matrices. It is shown that a circulant matrix can be multiplied by a vector in time O(n log(n)) in a ring with roots of unity without making use of…
cs.CC2019
Fast Commutative Matrix Algorithm
Andreas Rosowski
We show that the product of an nx3 matrix and a 3x3 matrix over a commutative ring can be computed using 6n+3 multiplications. For two 3x3 matrices this gives us an algorithm using…