Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets

Understand

Synchronization strings are recently introduced by Haeupler and Shahrasbi [HS17a] in the study of codes for correcting insertion and deletion errors (insdel codes).

• A synchronization string is an encoding of the indices of the symbols in a string, and together with an appropriate decoding algorithm it can transform insertion and deletion errors into standard symbol erasures and corruptions.
• This reduces the problem of constructing insdel codes to the problem of constructing standard error correcting codes, which is much better understood.
• Besides this, synchronization strings are also useful in other applications such as synchronization sequences and interactive coding schemes.