Back to Search
Start Over
Non-commutative lattice problems
- Publication Year :
- 2015
-
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.<br />Comment: 17 pages, 2 figures
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.1508.02388
- Document Type :
- Working Paper