34 citations · 112 across the 32 of their papers we have counts for
6 papers · 1 filter
Optimal Las Vegas reduction from one-way set reconciliation to error correction
Djamal Belazzougui
Suppose we have two players and , where player has a string and player has a string and none of the two players knows the other's string. Ass…
Efficient Deterministic Single Round Document Exchange for Edit Distance
Djamal Belazzougui
Suppose that we have two parties that possess each a binary string. Suppose that the length of the first string (document) is and that the two strings (documents) have edit dis…
Space-efficient detection of unusual words
Djamal Belazzougui, Fabio Cunial
Detecting all the strings that occur in a text more frequently or less frequently than expected according to an IID or a Markov model is a basic problem in string mining, yet curre…
Range Predecessor and Lempel-Ziv Parsing
Djamal Belazzougui, Simon J. Puglisi
The Lempel-Ziv parsing of a string (LZ77 for short) is one of the most important and widely-used algorithmic tools in data compression and string processing. We show that the Lempe…
A framework for space-efficient string kernels
Djamal Belazzougui, Fabio Cunial
String kernels are typically used to compare genome-scale sequences whose length makes alignment impractical, yet their computation is based on data structures that are either spac…
Composite repetition-aware data structures
Djamal Belazzougui, Fabio Cunial, Travis Gagie +2
In highly repetitive strings, like collections of genomes from the same species, distinct measures of repetition all grow sublinearly in the length of the text, and indexes targete…