Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem

DOI10.1016/j.jsc.2016.11.009zbMath1371.20037arXiv1501.05579OpenAlexW2553053200MaRDI QIDQ2628315

Volker Diekert, Armin Weiß, Alexei G. Myasnikov

Publication date: 1 June 2017

Published in: Journal of Symbolic Computation, Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.05579

zbMATH Keywords

HNN extensionsamenabilityamalgamated productsconjugacy problemSchreier graphsSchreier graphamenable graphsHNN extensiongeneric case complexityamalgamated producttime complexitiesstrongly generic algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Geometric group theory (20F65) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations (20E06) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Random walks on graphs (05C81)

Related Items

Average-case complexity without the black swans, Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem, Faithful group actions and Schreier graphs, Conjugacy in Baumslag's group, generic case complexity, and division in power circuits, The conjugacy problem for Higman’s group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The word problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable.
• Conjugacy in Baumslag's group, generic case complexity, and division in power circuits
• Random walks on graphs with a strong isoperimetric property
• Cogrowth and amenability of discrete groups
• Potential theory on infinite networks
• Generic-case complexity, decision problems in group theory, and random walks.
• Combinatorial group theory.
• Random walks on weakly hyperbolic groups
• Combinatorial group theory and public key cryptography
• Amenability of Schreier graphs and strongly generic algorithms for the conjugacy problem
• Cyclic rewriting and conjugacy problems
• Evolutionary algorithm solution of the multiple conjugacy search problem in groups, and its applications to cryptography
• On groups with full Banach mean value
• Full Banach Mean Values on Countable groups.
• Symmetric Random Walks on Groups
• Generic complexity of undecidable problems
• Orbit decidability and the conjugacy problem for some extensions of groups
• The Word Problem and Related Results for Graph Product Groups
• Cogrowth of Regular Graphs
• A Bound on Solutions of Linear Integer Equalities and Inequalities
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces
• Random Walks on Infinite Graphs and Groups
• Authentication from Matrix Conjugation
• GENERIC COMPLEXITY OF THE CONJUGACY PROBLEM IN HNN-EXTENSIONS AND ALGORITHMIC STRATIFICATION OF MILLER'S GROUPS
• Geodesic rewriting systems and pregroups