research
∙
08/24/2023
Complexity of Spherical Equations in Finite Groups
In this paper we investigate computational properties of the Diophantine...
share
research
∙
08/17/2023
Geodetic Graphs: Experiments and New Constructions
In 1962 Ore initiated the study of geodetic graphs. A graph is called ge...
research
∙
06/11/2022
Lower Bounds for Sorting 16, 17, and 18 Elements
It is a long-standing open question to determine the minimum number of c...
research
∙
01/17/2022
The Power Word Problem in Graph Products
The power word problem of a group G asks whether an expression p_1^x_1… ...
research
∙
10/03/2021
The isomorphism problem for plain groups is in Σ_3^𝖯
Testing isomorphism of infinite groups is a classical topic, but from th...
research
∙
02/19/2021
Parallel algorithms for power circuits and the word problem of the Baumslag group
Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Wo...
research
∙
10/22/2020
Equation satisfiability in solvable groups
The study of the complexity of the equation satisfiability problem in fi...
research
∙
02/24/2020
Hardness of equations over finite solvable groups under the exponential time hypothesis
Goldmann and Russell (2002) initiated the study of the complexity of the...
research
∙
09/30/2019
Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
We give lower bounds on the complexity of the word problem of certain no...
research
∙
05/23/2019
On the Average Case of MergeInsertion
MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting a...
research
∙
04/17/2019
The power word problem
In this work we introduce a new succinct variant of the word problem in ...
research
∙
11/03/2018
QuickXsort - A Fast Sorting Scheme in Theory and Practice
QuickXsort is a highly efficient in-place sequential sorting scheme that...
research
∙
11/02/2018
Worst-Case Efficient Sorting with QuickMergesort
The two most prominent solutions for the sorting problem are Quicksort a...
research
∙
04/26/2018
QuickMergesort: Practically Efficient Constant-Factor Optimal Sorting
We consider the fundamental problem of internally sorting a sequence of ...
research
∙
02/20/2018