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

DOI10.1016/j.jsc.2016.11.009zbMath1371.20037arXiv1501.05579MaRDI 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 extensions; amenability; amalgamated products; conjugacy problem; Schreier graphs; Schreier graph; amenable graphs; HNN extension; generic case complexity; amalgamated product; time complexities; strongly generic algorithms

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

20F65: Geometric group theory

05C25: Graphs and abstract algebra (groups, rings, fields, etc.)

20E06: Free products of groups, free products with amalgamation, Higman-Neumann-Neumann extensions, and generalizations

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

05C81: Random walks on graphs

Related Items

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

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