License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2019.37
URN: urn:nbn:de:0030-drops-102766
URL: https://drops.dagstuhl.de/opus/volltexte/2019/10276/
Go to the corresponding LIPIcs Volume Portal

Holt, Derek ; Lohrey, Markus ; Schleimer, Saul

Compressed Decision Problems in Hyperbolic Groups

pdf-format:
LIPIcs-STACS-2019-37.pdf (0.5 MB)

Abstract

We prove that the compressed word problem and the compressed simultaneous conjugacy problem are solvable in polynomial time in hyperbolic groups. In such problems, group elements are input as words defined by straight-line programs defined over a finite generating set for the group. We prove also that, for any infinite hyperbolic group G, the compressed knapsack problem in G is NP-complete.

BibTeX - Entry

@InProceedings{holt_et_al:LIPIcs:2019:10276,
  author =	{Derek Holt and Markus Lohrey and Saul Schleimer},
  title =	{{Compressed Decision Problems in Hyperbolic Groups}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Rolf Niedermeier and Christophe Paul},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10276},
  doi =		{10.4230/LIPIcs.STACS.2019.37},
  annote =	{Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems}
}

Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems
Collection: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Issue Date: 2019
Date of publication: 12.03.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI