Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartlomiej Dudek, Nick Fischer, Geri Gokaj, Ce Jin, Marvin Kunnemann, Xiao Mao, Mirza Redzic
To appear at STOC 2026
[arXiv]
Equivalences between Some Problems on Strings, Trees and Graphs
Bartlomiej Dudek
[PhD Dissertation]
2024
Slowing down top trees for better worst-case compression
Bartlomiej Dudek and Pawel Gawrychowski
Theor. Comput. Sci. (2024)
[arXiv, Conference version, Journal version, slides]
Online Context-Free Recognition in OMv Time
Bartlomiej Dudek and Pawel Gawrychowski
35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024)
[Publisher's version, slides]
Sorting Signed Permutations by Reversals in Nearly-Linear Time
Bartlomiej Dudek and Pawel Gawrychowski and Tatiana Starikovskaya
2024 Symposium on Simplicity in Algorithms (SOSA 2024)
[arXiv, Publisher's version, poster, slides]
Optimal Near-Linear Space Heaviest Induced Ancestors
Panagiotis Charalampopoulos and Bartlomiej Dudek and Pawel Gawrychowski and Karol Pokorski
34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
[arXiv, Publisher's version]
Streaming Regular Expression Membership and Pattern Matching
Bartlomiej Dudek and Pawel Gawrychowski and Garance Gourdel and Tatiana Starikovskaya
2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022)
[Publisher's version]
Strictly In-Place Algorithms for Permuting and Inverting Permutations
Bartlomiej Dudek and Pawel Gawrychowski and Karol Pokorski
Algorithms and Data Structures - 17th International Symposium (WADS 2021)
[arXiv, Publisher's version]
Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs
Bartlomiej Dudek and Pawel Gawrychowski
31st International Symposium on Algorithms and Computation (ISAAC 2020)
[arXiv, Publisher's version, slides]
Generalised Pattern Matching Revisited
Bartlomiej Dudek and Pawel Gawrychowski and Tatiana Starikovskaya
37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
[arXiv, Publisher's version, slides]
All non-trivial variants of 3-LDT are equivalent
Bartlomiej Dudek and Pawel Gawrychowski and Tatiana Starikovskaya
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020)
[arXiv, Publisher's version, slides, video]
Computing quartet distance is equivalent to counting 4-cycles
Bartlomiej Dudek and Pawel Gawrychowski
51st Annual ACM SIGACT Symposium on Theory of Computing (STOC 2019)
[arXiv, Publisher's version, poster, slides]
Slowing Down Top Trees for Better Worst-Case Compression
Bartlomiej Dudek and Pawel Gawrychowski
Annual Symposium on Combinatorial Pattern Matching (CPM 2018)
[arXiv, Publisher's version, Journal version, slides]
Edit Distance between Unrooted Trees in Cubic Time
Bartlomiej Dudek and Pawel Gawrychowski
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
[arXiv, Publisher's version, slides]
Universal protocols for information dissemination using emergent signals
Bartlomiej Dudek and Adrian Kosowski
50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018)
[arXiv, Publisher's version]
A Family of Approximation Algorithms for the Maximum Duo-Preservation String Mapping Problem
Bartlomiej Dudek and Pawel Gawrychowski and Piotr Ostropolski-Nalewaja
28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017)
[arXiv, Publisher's version, slides]
Robust Detection in Leak-Prone Population Protocols
Dan Alistarh and Bartlomiej Dudek and Adrian Kosowski and David Soloveichik and Przemyslaw Uznanski
DNA Computing and Molecular Programming - 23rd International Conference (DNA 2017)
[arXiv, Publisher's version]