I am a postdoc at the Max Planck Institute for Informatics, Germany, in the Algorithms and Complexity Department.
Prior to that, I was a postdoc at University of California, Berkeley, hosted by Barna Saha, and at the Bar-Ilan Univeristy, Israel, hosted by Ely Porat. In 2019, I defended my PhD thesis at the University of Warsaw.
E-mail address: kociumaka@mimuw.edu.pl
Public PGP key
Faster Approximate Pattern Matching: A Unified Approach
[DOI]
[arXiv]
, and
61st Annual Symposium on Foundations of Computer Science, FOCS 2020
Resolution of the Burrows-Wheeler Transform Conjecture
[DOI]
[arXiv]
and
61st Annual Symposium on Foundations of Computer Science, FOCS 2020
Sublinear-Time Algorithms for Computing & Embedding Gap Edit Distance
[DOI]
[arXiv]
and
61st Annual Symposium on Foundations of Computer Science, FOCS 2020
Small space and streaming pattern matching with k edits
[DOI]
[arXiv]
, and
62nd Annual Symposium on Foundations of Computer Science, FOCS 2021
Faster Pattern Matching under Edit Distance
[DOI]
[arXiv]
, and
63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
O(n + poly(k))-time Algorithm for Bounded Tree Edit Distance
[DOI]
[arXiv]
, , , , and
63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
Gap Edit Distance via Non-Adaptive Queries: Simple and Optimal
[DOI]
[arXiv]
, , and
63rd Annual Symposium on Foundations of Computer Science, FOCS 2022
Optimal Algorithms for Bounded Weighted Edit Distance
[arXiv]
, and
64th Annual Symposium on Foundations of Computer Science, FOCS 2023
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
[arXiv]
and
64th Annual Symposium on Foundations of Computer Science, FOCS 2023
Approximating Edit Distance in the Fully Dynamic Model
[arXiv]
, and
64th Annual Symposium on Foundations of Computer Science, FOCS 2023
Subquadratic-time algorithms for Abelian stringology problems
[DOI]
, and
AIMS Medical Science
Linear search by a pair of distinct-speed robots
[DOI]
, , , , , and
Algorithmica
String powers in trees
[DOI]
, , and
Algorithmica
Efficient indexes for jumbled pattern matching with constant-sized alphabet
[DOI]
, and
Algorithmica
Computing Longest Lyndon Subsequences and Longest Common Lyndon Subsequences
[DOI]
[arXiv]
, , , and
Algorithmica
Approximating upper degree-constrained partial orientations
[DOI]
[arXiv]
[pdf]
[slides]
and
Approximation, Randomization, and Combinatorial Optimization APPROX/RANDOM 2015
Improved Circular k-Mismatch Sketches
[DOI]
[arXiv]
, , , and
Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2020
An Improved Algorithm for the k-Dyck Edit Distance Problem
[DOI]
[arXiv]
, , , , and
33th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
How Compression and Approximation Affect Efficiency in String Distance Measures
[DOI]
[arXiv]
, , and
33th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2022
Approximating text-to-pattern Hamming distances
[DOI]
[arXiv]
, , , and
52nd Annual ACM Symposium on Theory of Computing, STOC 2020
Dynamic Suffix Array with Polylogarithmic Queries and Updates
[DOI]
[arXiv]
and
54th Annual ACM Symposium on Theory of Computing, STOC 2022
Weighted Edit Distance Computation: Strings, Trees, and Dyck
[arXiv]
, , , and
55th Annual ACM Symposium on Theory of Computing, STOC 2023
Improved Approximation Algorithms for Dyck Edit Distance and RNA Folding
[DOI]
[arXiv]
, and
49th International Colloquium on Automata, Languages, and Programming, ICALP 2022
Resolution of the Burrows-Wheeler transform conjecture
[DOI]
and
Communications of the ACM
Efficient enumeration of non-equivalent squares in partial words with few holes
[DOI]
[pdf]
, , , , , , and
Computing and Combinatorics, COCOON 2017
The maximum number of squares in a tree
[DOI]
[pdf]
[slides]
, , , , , , and
Combinatorial Pattern Matching, CPM 2012
Fast algorithm for partial covers in words
[DOI]
[pdf]
[slides]
, , , and
Combinatorial Pattern Matching, CPM 2013
Computing minimal and maximal suffixes of a substring revisited
[DOI]
[pdf]
, , and
Combinatorial Pattern Matching, CPM 2014
Efficient algorithms for shortest partial seeds in words
[DOI]
[pdf]
[slides]
, , , and
Combinatorial Pattern Matching, CPM 2014
Computing kth Lyndon word and decoding lexicographically minimal de Bruijn sequence
[DOI]
[pdf]
[slides]
, and
Combinatorial Pattern Matching, CPM 2014
Efficient index for weighted sequences
[DOI]
[arXiv]
[slides]
, , and
Combinatorial Pattern Matching, CPM 2016
Faster Longest Common Extension queries in strings over general alphabets
[DOI]
[arXiv]
, , and
Combinatorial Pattern Matching, CPM 2016
Minimal suffix and rotation of a substring in optimal time
[DOI]
[arXiv]
[slides]
Combinatorial Pattern Matching, CPM 2016
Linear-time algorithm for Long LCF with k mismatches
[DOI]
[arXiv]
, , , , , , and
Combinatorial Pattern Matching, CPM 2018
Quasi-linear-time algorithm for Longest Common Circular Factor
[DOI]
[arXiv]
, , , , , , , and
Combinatorial Pattern Matching, CPM 2019
Time-Space Tradeoffs for Finding a Long Common Substring
[DOI]
[arXiv]
, , and
Combinatorial Pattern Matching, CPM 2020
Dynamic String Alignment
[DOI]
, and
Combinatorial Pattern Matching, CPM 2020
Counting Distinct Patterns in Internal Dictionary Matching
[DOI]
[arXiv]
, , , , , , and
Combinatorial Pattern Matching, CPM 2020
The Streaming k-Mismatch Problem: Tradeoffs between Space and Total Time
[DOI]
[arXiv]
, , and
Combinatorial Pattern Matching, CPM 2020
Approximating Longest Common Substring with k Mismatches: Theory and Practice
[DOI]
[arXiv]
, , and
Combinatorial Pattern Matching, CPM 2020
A fast branching algorithm for Cluster Vertex Deletion
[DOI]
[pdf]
[slides]
, , and
Computer Science Symposium in Russia, CSR 2014
Maximum number of distinct and nonequivalent nonstandard squares in a word
[DOI]
[pdf]
, , and
Developments in Language Theory, DLT 2014
Tight Bound for the Number of Distinct Palindromes in a Tree
[DOI]
[arXiv]
, , and
Electronic Journal of Combinatorics
Efficient indexes for jumbled pattern matching with constant-sized alphabet
[DOI]
[pdf]
[slides]
, and
21st Annual European Symposium on Algorithms, ESA 2013
Sublinear space algorithms for the Longest Common Substring problem
[DOI]
[arXiv]
[pdf]
, and
22nd Annual European Symposium on Algorithms, ESA 2014
Approximating LZ77 via small-space multiple-pattern matching
[DOI]
[arXiv]
[pdf]
, , and
23rd Annual European Symposium on Algorithms, ESA 2015
Edit distance with block operations
[DOI]
, , and
26th Annual European Symposium on Algorithms, ESA 2018
Practical Performance of Space Efficient Data Structures for Longest Common Extensions
[DOI]
, , , and
28th Annual European Symposium on Algorithms, ESA 2020
Faster Algorithms for Longest Common Substring
[DOI]
[arXiv]
, , and
29th Annual European Symposium on Algorithms, ESA 2021
Approximate Circular Pattern Matching
[DOI]
[arXiv]
, , , , , and
30th Annual European Symposium on Algorithms, ESA 2022
Bellman-Ford Is Optimal for Shortest Hop-Bounded Paths
[DOI]
[arXiv]
and
31st Annual European Symposium on Algorithms, ESA 2023
Circular pattern matching with k mismatches
[DOI]
[arXiv]
, , , , , , and
Fundamentals of Computation Theory, FCT 2019
Algorithmics of repetitions, local periods and critical factorization revisited
[URL]
, , , , and
Festschrift for Bořivoj Melichar
Efficient representation and counting of antipower factors in words
[DOI]
[arXiv]
, , , , and
Information and Computation
Graph and string Parameters: Connections between pathwidth, cutwidth and the locality number
[DOI]
[arXiv]
, , , , and
Automata, Languages, and Programming, ICALP 2019
A note on efficient computation of all Abelian periods in a string
[DOI]
[arXiv]
[pdf]
, , , , , , , and
Information Processing Letters
On the greedy algorithm for the Shortest Common Superstring problem with reversals
[DOI]
[arXiv]
, , , and
Information Processing Letters
An LP-rounding 22-approximation for restricted maximum acyclic subgraph
[DOI]
[arXiv]
[pdf]
, and
Information Processing Letters
Efficient counting of square substrings in a tree
[DOI]
[pdf]
, , , and
23rd International Symposium on Algorithms and Computation, ISAAC 2012
Covering problems for partial words and for indeterminate strings
[DOI]
[pdf]
[slides]
, , , , and
Algorithms and Computation, ISAAC 2014
Pattern matching and consensus problems on weighted sequences and profiles
[DOI]
[slides]
, and
27th International Symposium on Algorithms and Computation, ISAAC 2016
Longest unbordered factor in quasilinear time
[DOI]
[arXiv]
, , and
29th International Symposium on Algorithms and Computation, ISAAC 2018
Internal Dictionary Matching
[DOI]
, , , , and
30th International Symposium on Algorithms and Computation, ISAAC 2019
Small-space algorithms for the online language distance problem for palindromes and squares
, and
34th International Symposium on Algorithms and Computation, ISAAC 2023
An Algorithmic Bridge Between Hamming and Levenshtein Distances
[DOI]
[arXiv]
, , and
14th Innovations in Theoretical Computer Science Conference, ITCS 2023
Computing Longest (Common) Lyndon Subsequences
[DOI]
[arXiv]
, , , and
33rd International Workshop on Combinatorial Algorithms, IWOCA 2022
Fast algorithms for Abelian periods in words and greatest common divisor queries
[DOI]
, and
Journal of Computer and System Sciences
Circular pattern matching with k mismatches
[DOI]
[arXiv]
, , , , , , and
Journal of Computer and System Sciences
A note on the longest common compatible prefix problem for partial words
[DOI]
[arXiv]
, , , , , , , and
Journal of Discrete Algorithms
Efficient enumeration of non-equivalent squares in partial words with few holes
[DOI]
, , , , , , and
Journal of Combinatorial Optimization
Linear-time version of Holub's algorithm for morphic imprimitivity testing
[DOI]
[pdf]
, , and
Language and Automata Theory and Applications, LATA 2013
On periodicity lemma for partial words
[DOI]
, , and
Language and Automata Theory and Applications, LATA 2018
Efficient representation and counting of antipower factors in words
[DOI]
[arXiv]
, , , , and
Language and Automata Theory and Applications, LATA 2019
Towards a Definitive Measure of Repetitiveness
[DOI]
[arXiv]
, and
Latin American Theoretical Informatics Symposium, LATIN 2020
Near-Optimal Search Time in δ-Optimal Space
[DOI]
[arXiv]
, and
Latin American Theoretical Informatics Symposium, LATIN 2022
Subquadratic-time algorithms for Abelian stringology problems
[DOI]
, and
Mathematical Aspects of Computer and Information Sciences, MACIS 2015
RLE edit distance in near optimal time
[DOI]
[arXiv]
, , , and
Mathematical Foundations of Computer Science, MFCS 2019
New and efficient approaches to the quasiperiodic characterisation of a string
[URL]
, , , , , and
Prague Stringology Conference 2012
Efficient ranking of Lyndon words and decoding lexicographically minimal de Bruijn sequence
[DOI]
[arXiv]
, and
SIAM Journal on Discrete Mathematics
Linear search by a pair of distinct-speed robots
[DOI]
, , , , , and
Structural Information and Communication Complexity, SIROCCO 2016
A linear time algorithm for seeds computation
[DOI]
[slides]
, , , and
23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Wavelet trees meet suffix trees
[DOI]
[arXiv]
[slides]
, , and
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Internal pattern matching queries in a text and applications
[DOI]
[arXiv]
[slides]
, , and
26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015
Sparse suffix tree construction in optimal time and space
[DOI]
[arXiv]
and
28th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017
Optimal dynamic strings
[DOI]
[arXiv]
[slides]
, , , and
29th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018
The streaming k-mismatch problem
[DOI]
[arXiv]
[slides]
, and
30th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays and Suffix Trees
[DOI]
[arXiv]
and
34th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2023
Efficient data structures for the factor periodicity problem
[DOI]
[pdf]
[slides]
, , and
String Processing and Information Retrieval, SPIRE 2012
Order-preserving incomplete suffix trees and order-preserving indexes
[DOI]
[pdf]
, , , , , , , and
String Processing and Information Retrieval, SPIRE 2013
On the string consensus problem and the Manhattan sequence consensus problem
[DOI]
[pdf]
, , , and
String Processing and Information Retrieval, SPIRE 2014
Efficient algorithms for Longest Closed Factor array
[DOI]
[pdf]
, , , , , , and
String Processing and Information Retrieval, SPIRE 2015
Tight bound for the number of distinct palindromes in a tree
[DOI]
[arXiv]
[pdf]
, , and
String Processing and Information Retrieval, SPIRE 2015
Near-optimal computation of runs over general alphabet via non-crossing LCE queries
[DOI]
[arXiv]
[slides]
, , , , , , and
String Processing and Information Retrieval, SPIRE 2016
On two LZ78-style grammars: compression bounds and compressed-space computation
[DOI]
[arXiv]
, , , , and
String Processing and Information Retrieval, SPIRE 2017
Faster recovery of approximate periods over edit distance
[DOI]
[arXiv]
, , , , and
String Processing and Information Retrieval, SPIRE 2018
Efficient computation of sequence mappability
[DOI]
[arXiv]
, , , , , and
String Processing and Information Retrieval, SPIRE 2018
Weighted Shortest Common Supersequence Problem Revisited
[DOI]
[arXiv]
, , , , , , and
String Processing and Information Retrieval, SPIRE 2019
On Longest Common Property Preserved Substring Queries
[DOI]
[arXiv]
, , , , and
String Processing and Information Retrieval, SPIRE 2019
Efficient Enumeration of Distinct Factors Using Package Representations
[DOI]
[pdf]
, , , , and
String Processing and Information Retrieval, SPIRE 2020
Fast algorithms for Abelian periods in words and greatest common divisor queries
[DOI]
[slides]
, and
Symposium on Theoretical Aspects of Computer Science, STACS 2013
Constant factor approximation for Capacitated k-Center with Outliers
[DOI]
[arXiv]
[slides]
and
Symposium on Theoretical Aspects of Computer Science, STACS 2014
String periods in the order-preserving model
[DOI]
, , , , and
Symposium on Theoretical Aspects of Computer Science, STACS 2018
String synchronizing sets: Sublinear-time BWT construction and optimal LCE data structure
[DOI]
[arXiv]
[slides]
and
51st Annual ACM Symposium on Theory of Computing, STOC 2019
Improved Dynamic Algorithms for Longest Increasing Subsequence
[DOI]
[arXiv]
and
53rd Annual ACM Symposium on Theory of Computing, STOC 2021
A linear time algorithm for seeds computation
[DOI]
[arXiv]
, , , and
ACM Transactions on Algorithms
An Improved Algorithm for the k-Dyck Edit Distance Problem
[DOI]
[arXiv]
, , , , and
ACM Transactions on Algorithms
Computing minimal and maximal suffixes of a substring
[DOI]
[arXiv]
, , , and
Theoretical Computer Science
Covering problems for partial words and for indeterminate strings
[DOI]
[arXiv]
, , , , and
Theoretical Computer Science
Universal reconstruction of a string
[DOI]
, , , and
Theoretical Computer Science
Efficient counting of square substrings in a tree
[DOI]
[pdf]
, , , and
Theoretical Computer Science
Linear-time version of Holub's algorithm for morphic imprimitivity testing
[DOI]
, , and
Theoretical Computer Science
Maximum number of distinct and nonequivalent nonstandard squares in a word
[DOI]
[arXiv]
, , and
Theoretical Computer Science
On the string consensus problem and the Manhattan sequence consensus problem
[DOI]
[arXiv]
, , , and
Theoretical Computer Science
Efficient algorithms for shortest partial seeds in words
[DOI]
, , , and
Theoretical Computer Science
Toward a Definitive Compressibility Measure for Repetitive Sequences
[DOI]
[arXiv]
, and
IEEE Transactions on Information Theory
A fast branching algorithm for Cluster Vertex Deletion
[DOI]
[arXiv]
, , and
Theory of Computing Systems
Pattern matching and consensus problems on weighted sequences and profiles
[DOI]
[arXiv]
, and
Theory of Computing Systems
Hardness of approximation for strip packing
[DOI]
[arXiv]
, , and
ACM Transactions on Computation Theory
Universal reconstruction of a string
[DOI]
[pdf]
[slides]
, , , and
Algorithms and Data Structures, WADS 2015
Linear Time Computation of Cyclic Roots and Cyclic Covers of a String
, , , , and
Combinatorial Pattern Matching, CPM 2023