Non-commutative lattice problems

Research output: Contribution to journalArticlepeer-review

7 Scopus citations

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 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.

Original languageEnglish
Pages (from-to)455-475
Number of pages21
JournalJournal of Group Theory
Volume19
Issue number3
DOIs
StatePublished - 1 May 2016

Fingerprint

Dive into the research topics of 'Non-commutative lattice problems'. Together they form a unique fingerprint.

Cite this