Non-commutative lattice problems

DOI10.1515/JGTH-2016-0506MaRDI QIDQ285583zbMATHOpenAlexFDO

Authors Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov

Publication date 19 May 2016

Published in Journal of Group Theory (Search for Journal in Brave)

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

zbMATH Keywords

Coxeter groupsgeodesicsnilpotent groupscomputational lattice problemssurface groups

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Reflection and Coxeter groups (group-theoretic aspects) (20F55) Geometric group theory (20F65) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Nilpotent groups (20F18)

Abstract: We consider several subgroup-related algorithmic questions in groups, modeled after the classic computational lattice problems, and study their computational complexity. We find polynomial time solutions to problems like finding a subgroup element closest to a given group element, or finding a shortest non-trivial element of a subgroup in the case of nilpotent groups, and a large class of surface groups and Coxeter groups. We also provide polynomial time algorithm to compute geodesics in given generators of a subgroup of a free group.

Recommendations

• Low-complexity computations for nilpotent subgroup problems
• Some geodesic problems in groups
• The word and generator problems for lattices
• The Nielsen reduction and P-complete problems in free groups
• Logspace and compressed-word computations in nilpotent groups

Cites work

• scientific article; zbMATH DE number 3871623 (Why is no real title available?)
• scientific article; zbMATH DE number 53661 (Why is no real title available?)
• scientific article; zbMATH DE number 845627 (Why is no real title available?)
• scientific article; zbMATH DE number 3335108 (Why is no real title available?)
• A FAST ALGORITHM FOR STALLINGS' FOLDING PROCESS
• A finiteness property and an automatic structure for Coxeter groups
• Artin groups of large type are shortlex automatic with regular geodesics.
• Combinatorics of Coxeter Groups
• Coxeter groups, 2-completion, perimeter reduction and subgroup separability.
• Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
• Growth of finitely generated solvable groups and curvature of Riemannian manifolds
• Knapsack problems in groups
• Knapsack problems in products of groups
• Logspace and compressed-word computations in nilpotent groups
• Logspace computations in graph groups and Coxeter groups.
• Polynomial-time word problems.
• The Post correspondence problem in groups.
• The word and geodesic problems in free solvable groups.

Cited in

(11)

• Non-abelian analogs of lattice rounding
• \(\mathsf{TC}^0\) circuits for algorithmic problems in nilpotent groups
• Logspace and compressed-word computations in nilpotent groups
• Cryptanalysis of a combinatorial public key cryptosystem
• scientific article; zbMATH DE number 4027530 (Why is no real title available?)
• Parallel complexity for nilpotent groups
• scientific article; zbMATH DE number 1263640 (Why is no real title available?)
• Subset sum problem in polycyclic groups
• APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
• On subset sum problem in branch groups
• Some geodesic problems in groups

This page was built for publication: Non-commutative lattice problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q285583)