Imagen de Portada

Linear average-case complexity of algorithmic problems in groups

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Olshanskii, Alexander, Shpilrain, Vladimir
Formato:	Preprint
Publicado:	2022
Materias:	Group Theory Computational Complexity 20F10, 68Q25
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

The average-case complexity of the Word Problem for groups of matrices over $\mathbb{Z}$ is linear
por: Bassino, Frédérique, et al.
Publicado: (2025)

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

A fast algorithm for Stallings foldings over virtually free groups
por: Cookson, Sam, et al.
Publicado: (2023)

On the complexity of epimorphism testing with virtually abelian targets
por: Elder, Murray, et al.
Publicado: (2025)

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

Parallel Algorithms for Group Isomorphism via Code Equivalence
por: Levet, Michael
Publicado: (2026)

Polynomial-time isomorphism test for groups with abelian Sylow subgroups
por: Skresanov, Saveliy V.
Publicado: (2026)

Complexity of some algorithmic problems in groups: a survey
por: Shpilrain, Vladimir
Publicado: (2024)

On isomorphisms to a free group and beyond
por: Shpilrain, Vladimir
Publicado: (2023)

On the ET0L subgroup membership problem in bounded automata groups
por: Bishop, Alex, et al.
Publicado: (2024)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
por: Ye, Lixi
Publicado: (2026)

Polynomial-time isomorphism test for $k$-generated extensions of abelian groups
por: Skresanov, Saveliy V.
Publicado: (2026)

On groups with EDT0L word problem
por: Bishop, Alex, et al.
Publicado: (2025)

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

Constrained inhomogeneous spherical equations: average-case hardness
por: Ushakov, Alexander
Publicado: (2024)

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

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

Quaternionic lattices and poly-context-free word problem
por: Bondarenko, Ievgen
Publicado: (2024)

Count-Free Weisfeiler--Leman and Group Isomorphism
por: Collins, Nathaniel A., et al.
Publicado: (2022)

On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
por: Grochow, Joshua A., et al.
Publicado: (2021)

The word problem and growth of groups
por: Bondarenko, Ievgen
Publicado: (2024)

Parameterized Complexity of Factorization Problems
por: Lohrey, Markus, et al.
Publicado: (2023)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
por: Avila, Tatiana Rocha, et al.
Publicado: (2026)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
por: Xia, Mingji
Publicado: (2026)

Conjugacy languages in virtual graph products
por: Crowe, Gemma
Publicado: (2022)

On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
por: Grochow, Joshua A., et al.
Publicado: (2025)

Cluster Vertex Deletion Problems on Cubic Graphs
por: Rusu, Irena
Publicado: (2025)

On weighted graph separation problems and flow-augmentation
por: Kim, Eun Jung, et al.
Publicado: (2022)

Quadratic equations in the lamplighter group
por: Ushakov, Alexander, et al.
Publicado: (2023)

Permutation closure for multiple context-free languages
por: Duncan, Andrew, et al.
Publicado: (2025)

Membership problems in braid groups and Artin groups
por: Gray, Robert D., et al.
Publicado: (2024)

Subsets of groups with context-free preimages
por: Levine, Alex
Publicado: (2023)

One-variable equations over the lamplighter group
por: Ushakov, Alexander, et al.
Publicado: (2026)

Streaming algorithms for groups and semigroups
por: Lohrey, Markus, et al.
Publicado: (2022)

The Word Problem for Finitary Automaton Groups
por: Kotowsky, Maximilian, et al.
Publicado: (2023)

Context-free graphs and their transition groups
por: D'Angeli, Daniele, et al.
Publicado: (2024)

The Word Problem for Products of Symmetric Groups
por: Simon, Hans U.
Publicado: (2025)

Regularity of quasigeodesics characterises hyperbolicity
por: Hughes, Sam, et al.
Publicado: (2022)

Groups with presentations in EDT0L
por: Bartholdi, Laurent, et al.
Publicado: (2024)