Showing 2026Show all
3 papers · 1 filter
math.GR2026
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…
cs.CC2026
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…
math.RA2026
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…