{
  "id": "1508.02388",
  "version": "v1",
  "published": "2015-08-10T20:02:10.000Z",
  "updated": "2015-08-10T20:02:10.000Z",
  "title": "Non-commutative lattice problems",
  "authors": [
    "Alexei Myasnikov",
    "Andrey Nikolaev",
    "Alexander Ushakov"
  ],
  "comment": "17 pages, 2 figures",
  "categories": [
    "math.GR",
    "cs.CC",
    "math.CO"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-08-10T20:02:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D15",
      "20F65",
      "20F10"
    ],
    "keywords": [
      "non-commutative lattice problems",
      "classic computational lattice problems",
      "polynomial time algorithm",
      "polynomial time solutions",
      "subgroup element closest"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv150802388M"
    }
  }
}