research
∙
08/30/2023
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Given a signed permutation on n elements, we need to sort it with the fe...
share
research
∙
02/02/2023
Optimal Heaviest Induced Ancestors
We revisit the Heaviest Induced Ancestors (HIA) problem that was introdu...
research
∙
01/11/2021
Strictly In-Place Algorithms for Permuting and Inverting Permutations
We revisit the problem of permuting an array of length n according to a ...
research
∙
10/01/2020
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
Permutation σ appears in permutation π if there exists a subsequence of ...
research
∙
01/16/2020
Generalised Pattern Matching Revisited
In the problem of Generalised Pattern Matching (GPM) [STOC'94, Muthukris...
research
∙
01/05/2020
All non-trivial variants of 3-LDT are equivalent
The popular 3-SUM conjecture states that there is no strongly subquadrat...
research
∙
11/15/2018
Computing Quartet Distance is Equivalent to Counting 4-Cycles
The quartet distance is a measure of similarity used to compare two unro...
research
∙
04/26/2018
Edit Distance between Unrooted Trees in Cubic Time
Edit distance between trees is a natural generalization of the classical...
research
∙
01/03/2018