The Library
Compressed decision problems in hyperbolic groups
Tools
Holt, Derek F., Lohrey, Markus and Schleimer, Saul (2018) Compressed decision problems in hyperbolic groups. In: 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019), Berlin, Germany, 13–16 Mar 2019. Published in: Leibniz International Proceedings in Informatics (LIPIcs) 34:1-34:16. doi:10.4230/LIPIcs.STACS.2019.34 ISSN 1868-8969.
|
PDF
WRAP-compressed-decision-problems-hyperbolic-groups-Holt-2018.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Public Domain Dedication. Download (443Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.STACS.2019.34
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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Mathematics | ||||||
Library of Congress Subject Headings (LCSH): | Hyperbolic groups, Cryptography | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 20 December 2018 | ||||||
Dates: |
|
||||||
Page Range: | 34:1-34:16 | ||||||
Article Number: | 34 | ||||||
DOI: | 10.4230/LIPIcs.STACS.2019.34 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 3 January 2019 | ||||||
Date of first compliant Open Access: | 16 January 2019 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Berlin, Germany | ||||||
Date(s) of Event: | 13–16 Mar 2019 | ||||||
Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year