Cover Image

Complexity of some algorithmic problems in groups: a survey

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Shpilrain, Vladimir
Format:	Preprint
Published:	2024
Subjects:	Group Theory Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Linear average-case complexity of algorithmic problems in groups
by: Olshanskii, Alexander, et al.
Published: (2022)

Orbit-blocking words in free groups
by: Koch-Hyde, Lucy, et al.
Published: (2025)

Orbit-blocking words and the average-case complexity of Whitehead's problem in the free group of rank 2
by: Hyde, Lucy, et al.
Published: (2024)

On the complexity of the word problem of the R. Thompson group V
by: Birget, J. C.
Published: (2022)

Automorphic orbits in free groups: recent progress
by: Shpilrain, Vladimir
Published: (2025)

The hidden subgroup problem for infinite groups
by: Kuperberg, Greg
Published: (2025)

HNN extensions of free groups with equal associated subgroups of finite index: polynomial time word problem
by: Shen, Hanwen, et al.
Published: (2025)

Knot invariants from representations of braids by automorphisms of a free group
by: Shpilrain, Vladimir
Published: (2025)

The complexity of knapsack problems in wreath products
by: Figelius, Michael, et al.
Published: (2020)

On isomorphisms to a free group and beyond
by: Shpilrain, Vladimir
Published: (2023)

Word problems and embedding-obstructions in cellular automata groups on groups
by: Salo, Ville
Published: (2025)

Distortion element in the automorphism group of a full shift
by: Callard, Antonin, et al.
Published: (2022)

Ordering groups and the Identity Problem
by: Bodart, Corentin, et al.
Published: (2024)

Obstruction theory and the complexity of counting group homomorphisms
by: Samperton, Eric, et al.
Published: (2026)

The Identity Problem in the special affine group of $\mathbb{Z}^2$
by: Dong, Ruiwen
Published: (2023)

Girth of the Cayley graph and Cayley hash functions
by: Shpilrain, Vladimir
Published: (2025)

Some properties of Higman-Thompson monoids and digital circuits
by: Birget, J. C.
Published: (2024)

The central tree property and algorithmic problems on subgroups of free groups
by: Roy, Mallika, et al.
Published: (2023)

On the Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
by: Johnson, Dan, et al.
Published: (2025)

Reduction of the group isomorphism problem to the group automorphism problem
by: Skresanov, Saveliy V.
Published: (2025)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
by: Levet, Michael, et al.
Published: (2025)

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs
by: Dikstein, Yotam, et al.
Published: (2024)

On the Constant-Depth Circuit Complexity of Generating Quasigroups
by: Collins, Nathaniel A., et al.
Published: (2024)

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
by: Dwivedi, Prateek, et al.
Published: (2026)

Easy estimates of Lyapunov exponents for random products of matrices
by: Nabahi, Nadya, et al.
Published: (2025)

Growth in products of matrices: fastest, average, and generic
by: Shpilrain, Vladimir
Published: (2024)

Computational Complexity of Finding Subgroups of a Given Order
by: Lakshmanan, K.
Published: (2025)

Remembering Mark Sapir
by: Birget, Jean-Camille, et al.
Published: (2024)

Avoshifts
by: Salo, Ville
Published: (2024)

On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
by: Nosan, Klara, et al.
Published: (2021)

Efficient Compression in Semigroups
by: Thumm, Alexander, et al.
Published: (2026)

Group Order is in QCMA
by: Gall, François Le, et al.
Published: (2025)

Isometry groups of infinite-genus hyperbolic surfaces
by: Aougab, Tarik, et al.
Published: (2020)

Twisted conjugacy in dihedral Artin groups I: Torus Knot groups
by: Crowe, Gemma
Published: (2024)

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime
by: Mittal, Tushant, et al.
Published: (2024)

Membership and Conjugacy in Inverse Semigroups
by: Fleischer, Lukas, et al.
Published: (2025)

Twisted conjugacy in dihedral Artin groups II: Baumslag Solitar groups $\mathrm{BS}(n,n)$
by: Crowe, Gemma
Published: (2024)

Coboundary expansion of coset complexes
by: Kaufman, Tali, et al.
Published: (2024)

Uniqueness theorem for completely non-degenerate B-groups
by: Glutsyuk, A. A., et al.
Published: (2025)

On the Complexity of Problems on Graphs Defined on Groups
by: Das, Bireswar, et al.
Published: (2025)