6 citations · 14 across the 8 of their papers we have counts for
13 papers
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…
Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
Bartłomiej Dudek, Paweł Gawrychowski, Tatiana Starikovskaya
The popular 3SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements su…
Computing Quartet Distance is Equivalent to Counting 4-Cycles
Bartłomiej Dudek, Paweł Gawrychowski
The quartet distance is a measure of similarity used to compare two unrooted phylogenetic trees on the same set of leaves, defined as the number of subsets of four leaves relat…
Edit Distance between Unrooted Trees in Cubic Time
Bartłomiej Dudek, Paweł Gawrychowski
Edit distance between trees is a natural generalization of the classical edit distance between strings, in which the allowed elementary operations are contraction, uncontraction an…
Slowing Down Top Trees for Better Worst-Case Bounds
Bartłomiej Dudek, Paweł Gawrychowski
We consider the top tree compression scheme introduced by Bille et al. [ICALP 2013] and construct an infinite family of trees on nodes labeled from an alphabet of size , for…
Robust Detection in Leak-Prone Population Protocols
Dan Alistarh, Bartłomiej Dudek, Adrian Kosowski +2
In contrast to electronic computation, chemical computation is noisy and susceptible to a variety of sources of error, which has prevented the construction of robust complex system…
Universal Protocols for Information Dissemination Using Emergent Signals
Bartlomiej Dudek, Adrian Kosowski
We consider a population of agents which communicate with each other in a decentralized manner, through random pairwise interactions. One or more agents in the population may a…
A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem
Bartłomiej Dudek, Paweł Gawrychowski, Piotr Ostropolski-Nalewaja
In the Maximum Duo-Preservation String Mapping problem we are given two strings and wish to map the letters of the former to the letters of the latter so as to maximise the number…