6 papers
Obstruction theory and the complexity of counting group homomorphisms
Eric Samperton, Armin Weiß
Fix a finite group . We study the computational complexity of counting problems of the following flavor: given a group , count the number of homomorphisms . Our first…
The complexity of finding coset-generating polymorphisms and the promise metaproblem
Manuel Bodirsky, Armin Weiß
We show that the metaproblem for coset-generating polymorphisms is NP-complete, answering a question of Chen and Larose: given a finite structure, the computational question is whe…
Efficient Compression in Semigroups
Florian Stober, Alexander Thumm, Armin Weiß
Straight-line programs are a central tool in several areas of computer science, including data compression, algebraic complexity theory, and the algorithmic solution of algebraic e…
Membership and Conjugacy in Inverse Semigroups
Lukas Fleischer, Florian Stober, Alexander Thumm +1
The membership problem for an algebraic structure asks whether a given element is contained in some substructure, which is usually given by generators. In this work we study the me…
On the complexity of epimorphism testing with virtually abelian targets
Murray Elder, Jerry Shen, Armin Weiß
Friedl and Löh (2021, Confl. Math.) prove that testing whether or not there is an epimorphism from a finitely presented group to a virtually cyclic group, or to the direct product…
Finite groups with geodetic Cayley graphs
Murray Elder, Adam Piggott, Florian Stober +2
A connected undirected graph is called \emph{geodetic} if for every pair of vertices there is a unique shortest path connecting them. It has been conjectured that for finite groups…