Document Open Access Logo

Compressed Decision Problems in Hyperbolic Groups

Authors Derek Holt, Markus Lohrey, Saul Schleimer

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2019.37.pdf
  • Filesize: 495 kB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Algebraic complexity theory
Keywords
  • hyperbolic groups
  • algorithms for compressed words
  • circuit evaluation problems

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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 Get BibTex

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) https://doi.org/10.4230/LIPIcs.STACS.2019.37

Author Details

Derek Holt
  • University of Warwick, UK
Markus Lohrey
  • Universität Siegen, Germany
Saul Schleimer
  • University of Warwick, UK

Funding

  • Lohrey, Markus: has been supported by the DFG research project LO 748/12-1.

References

  1. Ian Agol. The virtual Haken conjecture. Documenta Mathematica, 18:1045-1087, 2013. With an appendix by Ian Agol, Daniel Groves, and Jason Manning. Google Scholar
  2. László Babai and Endre Szemerédi. On the complexity of matrix group problems I. In Proceedings of the 25th Annual Symposium on Foundations of Computer Science, FOCS 1984, pages 229-240. IEEE Computer Society, 1984. Google Scholar
  3. Gilbert Baumslag, Alexei G. Myasnikov, and Vladimir Shpilrain. Open problems in combinatorial group theory. In Combinatorial and geometric group theory, pages 1-38. American Mathematical Society, 2002. Google Scholar
  4. Martin Beaudry, Pierre McKenzie, Pierre Péladeau, and Denis Thérien. Finite Monoids: From Word to Circuit Evaluation. SIAM Journal on Computing, 26(1):138-152, 1997. Google Scholar
  5. David J. Buckley and Derek F. Holt. The conjugacy problem in hyperbolic groups for finite lists of group elements. International Journal of Algebra and Computation, 23(5):1127-1150, 2013. Google Scholar
  6. Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, Amit Sahai, and Abhi Shelat. The smallest grammar problem. IEEE Transactions on Information Theory, 51(7):2554-2576, 2005. Google Scholar
  7. François Dahmani and Vincent Guirardel. The Isomorphism Problem for All Hyperbolic Groups. Geometric and Functional Analysis, 21(2):223-300, 2011. Google Scholar
  8. Max Dehn. Über unendliche diskontinuierliche Gruppen. Mathematische Annalen, 71:116-144, 1911. Google Scholar
  9. Volker Diekert, Jürn Laun, and Alexander Ushakov. Efficient Algorithms for Highly Compressed Data: the Word Problem in Higman’s Group is in P. International Journal of Algebra and Computation, 22(8), 2012. Google Scholar
  10. Will Dison, Eduard Einstein, and Timothy R. Riley. Ackermannian Integer Compression and the Word Problem for Hydra Groups. In Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, volume 58 of LIPIcs, pages 30:1-30:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. Google Scholar
  11. David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston. Word Processing in Groups. Jones and Bartlett, 1992. Google Scholar
  12. David B. A Epstein and Derek F. Holt. The Linearity of the Conjugacy Problem in Word-hyperbolic Groups. International Journal of Algebra and Computation, 16(2):287-306, 2006. Google Scholar
  13. Elizaveta Frenkel, Andrey Nikolaev, and Alexander Ushakov. Knapsack problems in products of groups. Journal of Symbolic Computation, 74:96-108, 2016. Google Scholar
  14. Moses Ganardi, Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack Problems for Wreath Products. In Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, volume 96 of LIPIcs, pages 32:1-32:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  15. Max Garzon and Yechezkel Zalcstein. The complexity of Grigorchuk groups with application to cryptography. Theoretical Computer Science, 88(1):83-98, 1991. Google Scholar
  16. Mikhail Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in Group Theory, number 8 in MSRI Publ., pages 75-263. Springer, 1987. Google Scholar
  17. Christoph Haase. On the complexity of model checking counter automata. PhD thesis, University of Oxford, St Catherine’s College, 2011. Google Scholar
  18. Christian Hagenah. Gleichungen mit regulären Randbedingungen über freien Gruppen. PhD thesis, University of Stuttgart, 2000. Google Scholar
  19. Frédéric Haglund and Daniel T. Wise. Coxeter groups are virtually special. Advances in Mathematics, 224(5):1890-1903, 2010. Google Scholar
  20. Nico Haubold, Markus Lohrey, and Christian Mathissen. Compressed decision problems for graph products of groups and applications to (outer) automorphism groups. International Journal of Algebra and Computation, 22(8), 2013. Google Scholar
  21. Derek F. Holt. Word-hyperbolic groups have real-time word problem. International Journal of Algebra and Computation, 10:221-228, 2000. Google Scholar
  22. Derek F. Holt, Markus Lohrey, and Saul Schleimer. Compressed decision problems in hyperbolic groups. CoRR, 2018. URL: http://arxiv.org/abs/1808.06886.
  23. Derek F. Holt, Sarah Rees, and Claas E. Röver. Groups, Languages and Automata, volume 88 of London Mathematical Society Student Texts. Cambridge University Press, 2017. Google Scholar
  24. Russell Impagliazzo and Avi Wigderson. P = BPP if E requires exponential circuits: Derandomizing the XOR lemma. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computing, STOC 1997, pages 220-229. ACM, 1997. Google Scholar
  25. Martin Kassabov and Francesco Matucci. The simultaneous conjugacy problem in groups of piecewise linear functions. Groups, Geometry, and Dynamics, 6(2):279-315, 2012. Google Scholar
  26. Daniel König and Markus Lohrey. Evaluation of circuits over nilpotent and polycyclic groups. Algorithmica, 80(5):1459-1492, 2018. Google Scholar
  27. Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. In Algebra and Computer Science, volume 677 of Contemporary Mathematics, pages 138-153. American Mathematical Society, 2016. Google Scholar
  28. Markus Lohrey. Word problems and membership problems on compressed words. SIAM Journal on Computing, 35(5):1210-1240, 2006. Google Scholar
  29. Markus Lohrey. Algorithmics on SLP-Compressed Strings: A Survey. Groups Complexity Cryptology, 4(2):241-299, 2012. Google Scholar
  30. Markus Lohrey. The Compressed Word Problem for Groups. SpringerBriefs in Mathematics. Springer, 2014. Google Scholar
  31. Markus Lohrey. Knapsack in Hyperbolic Groups. In Proceedings of the 12th International Conference on Reachability Problems, RP 2018, volume 11123 of Lecture Notes in Computer Science, pages 87-102. Springer, 2018. Google Scholar
  32. Markus Lohrey and Georg Zetzsche. Knapsack in Graph Groups. Theory of Computing Systems, 62(1):192-246, 2018. Google Scholar
  33. Jeremy Macdonald. Compressed words and automorphisms in fully residually free groups. International Journal of Algebra and Computation, 20(3):343-355, 2010. Google Scholar
  34. Jeremy MacDonald, Alexei G. Myasnikov, and Denis Ovchinnikov. Low-complexity computations for nilpotent subgroup problems. CoRR, abs/1706.01092, 2017. URL: http://arxiv.org/abs/1706.01092.
  35. Alexei G. Myasnikov, Andrey Nikolaev, and Alexander Ushakov. Knapsack Problems in Groups. Mathematics of Computation, 84:987-1016, 2015. Google Scholar
  36. Alexei G. Myasnikov, Alexander Ushakov, and Dong Wook Won. The Word Problem in the Baumslag group with a non-elementary Dehn function is polynomial time decidable. Journal of Algebra, 345(1):324-342, 2011. Google Scholar
  37. Alexei G. Myasnikov, Alexander Ushakov, and Dong Wook Won. Power circuits, exponential algebra, and time complexity. International Journal of Algebra and Computation, 22(6), 2012. Google Scholar
  38. Alexander Yu. Ol’shanskii. Almost every group is hyperbolic. International Journal of Algebra and Computation, 2(1):1-17, 1992. Google Scholar
  39. Wojciech Plandowski. Testing Equivalence of Morphisms on Context-Free Languages. In Proceedings of the 2nd Annual European Symposium on Algorithms, ESA 1994, volume 855 of Lecture Notes in Computer Science, pages 460-470. Springer, 1994. Google Scholar
  40. Saul Schleimer. Polynomial-time word problems. Commentarii Mathematici Helvetici, 83(4):741-765, 2008. Google Scholar
  41. Nicholas W. M. Touikan. A Fast Algorithm for Stallings' Folding Process. International Journal of Algebra and Computation, 16(6):1031-1046, 2006. Google Scholar
  42. Stephan Waack. The Parallel Complexity of Some Constructions in Combinatorial Group Theory. Journal of Information Processing and Cybernetics EIK, 26:265-281, 1990. Google Scholar
  43. Daniel T. Wise. Research announcement: the structure of groups with a quasiconvex hierarchy. Electronic Research Announcements in Mathematical Sciences, 16:44-55, 2009. Google Scholar
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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact