2 citations · 2 across the 4 of their papers we have counts for
13 papers · 1 filter
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek, Nick Fischer, Geri Gokaj +4
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schul…
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
Given a signed permutation on elements, we need to sort it with the fewest reversals. This is a fundamental algorithmic problem motivated by applications in comparative genomic…
Optimal Heaviest Induced Ancestors
Panagiotis Charalampopoulos, Bartłomiej Dudek, Paweł Gawrychowski +1
We revisit the Heaviest Induced Ancestors (HIA) problem that was introduced by Gagie, Gawrychowski, and Nekrich [CCCG 2013] and has a number of applications in string algorithms. L…
Strictly In-Place Algorithms for Permuting and Inverting Permutations
Bartłomiej Dudek, Paweł Gawrychowski, Karol Pokorski
We revisit the problem of permuting an array of length according to a given permutation in place, that is, using only a small number of bits of extra storage. Fich, Munro and P…
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
Bartłomiej Dudek, Paweł Gawrychowski
Permutation appears in permutation if there exists a subsequence of that is order-isomorphic to . The natural question is to check if appears in , and if so c…
Generalised Pattern Matching Revisited
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
In the problem of [STOC'94, Muthukrishnan and Palem], we are given a text of length over an alphabet , a patter…