research
∙
05/04/2022
Sketching Approximability of (Weak) Monarchy Predicates
We analyze the sketching approximability of constraint satisfaction prob...
share
research
∙
01/03/2021
Synchronization Strings and Codes for Insertions and Deletions – a Survey
Already in the 1960s, Levenshtein and others studied error-correcting co...
research
∙
09/28/2020
Rate-Distance Tradeoffs for List-Decodable Insertion-Deletion Codes
This paper presents general bounds on the highest achievable rate for li...
research
∙
09/24/2019
Optimally Resilient Codes for List-Decoding from Insertions and Deletions
We give a complete answer to the following basic question: "What is the ...
research
∙
10/28/2018
Near-Linear Time Insertion-Deletion Codes and (1+ε)-Approximating Edit Distance via Indexing
We introduce fast-decodable indexing schemes for edit distance which can...
research
∙
03/08/2018
Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets
Synchronization strings are recently introduced by Haeupler and Shahrasb...
research
∙
02/23/2018