Armin Weiß

CoRR, January, 2025

Violating Constant Degree Hypothesis Requires Breaking Symmetry.

[BibT_eX]

[DOI]

Piotr Kawalek

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Membership and Conjugacy in Inverse Semigroups.

[BibT_eX]

[DOI]

Proceedings of the 52nd International Colloquium on Automata, Languages, and Programming, 2025

2024

Equation Satisfiability in Solvable Groups.

[BibT_eX]

[DOI]

Theory Comput. Syst., August, 2024

The Power Word Problem in Graph Products.

[BibT_eX]

[DOI]

Markus Lohrey

Theory Comput. Syst., June, 2024

Finite groups with geodetic Cayley graphs.

[BibT_eX]

[DOI]

CoRR, 2024

Complexity of Spherical Equations in Finite Groups.

[BibT_eX]

[DOI]

Caroline Mattes

Alexander Ushakov

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

Constant Depth Circuit Complexity for Generating Quasigroups.

[BibT_eX]

[DOI]

Proceedings of the 2024 International Symposium on Symbolic and Algebraic Computation, 2024

Scalable Ultrafast Almost-optimal Euclidean Shortest Paths.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Third International Joint Conference on Artificial Intelligence, 2024

2023

Geodetic Graphs: Experiments and New Constructions.

[BibT_eX]

[DOI]

CoRR, 2023

Lower Bounds for Sorting 16, 17, and 18 Elements.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Algorithm Engineering and Experiments, 2023

2022

Groups with ALOGTIME-hard Word Problems and PSPACE-complete Compressed Word Problems.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, December, 2022

Parallel complexity for nilpotent groups.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2022

The Isomorphism Problem for Plain Groups Is in Σ₃𝖯.

[BibT_eX]

[DOI]

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Improved Parallel Algorithms for Generalized Baumslag Groups.

[BibT_eX]

[DOI]

Caroline Mattes

Proceedings of the LATIN 2022: Theoretical Informatics, 2022

Satisfiability Problems for Finite Groups.

[BibT_eX]

[DOI]

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

The Power Word Problem in Graph Products.

[BibT_eX]

[DOI]

Proceedings of the Developments in Language Theory - 26th International Conference, 2022

2021

The isomorphism problem for plain groups is in Σ3P.

[BibT_eX]

[DOI]

CoRR, 2021

Parallel Algorithms for Power Circuits and the Word Problem of the Baumslag Group.

[BibT_eX]

[DOI]

Caroline Mattes

Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science, 2021

2020

QuickXsort: A Fast Sorting Scheme in Theory and Practice.

[BibT_eX]

[DOI]

Sebastian Wild

Algorithmica, 2020

An Automaton Group with PSPACE-Complete Word Problem.

[BibT_eX]

[DOI]

Jan Philipp Wächter

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science, 2020

Hardness of Equations over Finite Solvable Groups Under the Exponential Time Hypothesis.

[BibT_eX]

[DOI]

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Groups with ALOGTIME-Hard Word Problems and PSPACE-Complete Circuit Value Problems.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in TC 0.

[BibT_eX]

[DOI]

Alexei Miasnikov

Svetla Vassileva

Theory Comput. Syst., 2019

The Power Word Problem.

[BibT_eX]

[DOI]

Markus Lohrey

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science, 2019

On the Average Case of MergeInsertion.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 30th International Workshop, 2019

Worst-Case Efficient Sorting with QuickMergesort.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, 2019

2018

QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting.

[BibT_eX]

[DOI]

CoRR, 2018

The Isomorphism Problem for Finite Extensions of Free Groups Is In PSPACE.

[BibT_eX]

[DOI]

Géraud Sénizergues

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

TC^0 circuits for algorithmic problems in nilpotent groups.

[BibT_eX]

[DOI]

CoRR, 2017

TC0 Circuits for Algorithmic Problems in Nilpotent Groups.

[BibT_eX]

[DOI]

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

The Conjugacy Problem in Free Solvable Groups and Wreath Products of Abelian Groups is in $${{\mathsf {T}}}{{\mathsf {C}}}^0$$.

[BibT_eX]

[DOI]

Alexei Miasnikov

Svetla Vassileva

Proceedings of the Computer Science - Theory and Applications, 2017

2016

The conjugacy problem in free solvable groups and wreath product of abelian groups is in TC$^0$.

[BibT_eX]

[DOI]

Alexei Miasnikov

Svetla Vassileva

CoRR, 2016

BlockQuicksort: How Branch Mispredictions don't affect Quicksort.

[BibT_eX]

[DOI]

CoRR, 2016

BlockQuicksort: Avoiding Branch Mispredictions in Quicksort.

[BibT_eX]

[DOI]

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups.

[BibT_eX]

[DOI]

Proceedings of the Algebra and Computer Science, 2016

2015

On the complexity of conjugacy in amalgamated products and HNN extensions.

[BibT_eX]

[DOI]

PhD thesis, 2015

Amenability of Schreier Graphs and Strongly Generic Algorithms for the Conjugacy Problem.

[BibT_eX]

[DOI]

Proceedings of the 2015 ACM on International Symposium on Symbolic and Algebraic Computation, 2015

2014

Conjugacy in Baumslag's Group, Generic Case Complexity, and Division in Power Circuits.

[BibT_eX]

[DOI]

Proceedings of the LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31, 2014

QuickXsort: Efficient Sorting with n logn - 1.399n + o(n) Comparisons on Average.

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2014

2013

Context-Free Groups and their Structure Trees.

[BibT_eX]

[DOI]

Int. J. Algebra Comput., 2013

QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average.

[BibT_eX]

[DOI]

CoRR, 2013

Weak Heaps and Friends: Recent Developments.

[BibT_eX]

[DOI]

Proceedings of the Combinatorial Algorithms - 24th International Workshop, 2013

QuickHeapsort: Modifications and Improved Analysis.

[BibT_eX]

[DOI]