Non-commutative lattice problems

DOI10.1515/JGTH-2016-0506zbMATH Open1392.20028arXiv1508.02388OpenAlexW2963673714MaRDI QIDQ285583FDOQ285583

Authors: Alexei Myasnikov, Andrey Nikolaev, Alexander Ushakov 

Publication date: 19 May 2016

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

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.

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

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

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)

Cites Work

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

Cited In (11)

• Subset sum problem in polycyclic groups
• On subset sum problem in branch groups
• Title not available (Why is that?)
• Logspace and compressed-word computations in nilpotent groups
• Parallel complexity for nilpotent groups
• Title not available (Why is that?)
• APPROXIMATION OF GEODESICS IN METABELIAN GROUPS
• Non-abelian analogs of lattice rounding
• Some geodesic problems in groups
• Cryptanalysis of a combinatorial public key cryptosystem
• TC^0 circuits for algorithmic problems in nilpotent 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)