14 citations · 74 across the 41 of their papers we have counts for
4 papers · 2 filters
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…
Streaming algorithms for groups and semigroups
Markus Lohrey, Lukas Lück, Alexander Thumm +1
We investigate deterministic and randomized streaming algorithms for word problems in finitely generated groups and semigroups. For this we introduce the notion of a distinguisher:…
Exponent equations in HNN-extensions
Michael Figelius, Markus Lohrey
We consider exponent equations in finitely generated groups. These are equations, where the variables appear as exponents of group elements and take values from the natural numbers…
The Power Word Problem in Graph Products
Markus Lohrey, Florian Stober, Armin Weiß
The power word problem for a group asks whether an expression , where the are words over a finite set of generators of and the binar…