TY - JOUR
T1 - Non-commutative lattice problems
AU - Myasnikov, Alexei
AU - Nikolaev, Andrey
AU - Ushakov, Alexander
N1 - Publisher Copyright:
© 2016 by De Gruyter.
PY - 2016/5/1
Y1 - 2016/5/1
N2 - 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 nontrivial 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.
AB - 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 nontrivial 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.
UR - http://www.scopus.com/inward/record.url?scp=84969523539&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84969523539&partnerID=8YFLogxK
U2 - 10.1515/jgth-2016-0506
DO - 10.1515/jgth-2016-0506
M3 - Article
AN - SCOPUS:84969523539
SN - 1433-5883
VL - 19
SP - 455
EP - 475
JO - Journal of Group Theory
JF - Journal of Group Theory
IS - 3
ER -