1 Search Results for "Holt, Derek"

Document
DOI: 10.4230/LIPIcs.STACS.2019.37
Compressed Decision Problems in Hyperbolic Groups

Authors: Derek Holt, Markus Lohrey, and Saul Schleimer

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

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

Derek Holt, Markus Lohrey, and Saul Schleimer. Compressed Decision Problems in Hyperbolic Groups. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{holt_et_al:LIPIcs.STACS.2019.37,
  author =	{Holt, Derek and Lohrey, Markus and Schleimer, Saul},
  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 =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.37},
  URN =		{urn:nbn:de:0030-drops-102766},
  doi =		{10.4230/LIPIcs.STACS.2019.37},
  annote =	{Keywords: hyperbolic groups, algorithms for compressed words, circuit evaluation problems}
}
  • Refine by Author
  • 1 Holt, Derek
  • 1 Lohrey, Markus
  • 1 Schleimer, Saul

  • Refine by Classification
  • 1 Theory of computation → Algebraic complexity theory

  • Refine by Keyword
  • 1 algorithms for compressed words
  • 1 circuit evaluation problems
  • 1 hyperbolic groups

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2019

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact