2 citations · 2 across the 4 of their papers we have counts for
6 papers
On the Subgroup Distance Problem in Cyclic Permutation Groups
Andreas Rosowski
We show that the Subgroup distance problem regarding the Hamming distance, the Cayley distance and the distance is NP-complete when the input group is cyclic. When we re…
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…
Parameterized Complexity of Factorization Problems
Markus Lohrey, Andreas Rosowski
We study the parameterized complexity of the following factorization problem: given elements of a monoid and a parameter , can be written as the product…
Membership Problems in Finite Groups
Markus Lohrey, Andreas Rosowski, Georg Zetzsche
We show that the subset sum problem, the knapsack problem and the rational subset membership problem for permutation groups are NP-complete. Concerning the knapsack problem we obta…
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…
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…