Clark School Home UMD

ISR Events Calendar

Event Information

CCSP Seminar: Ke Wu, "Synchronization Strings: Highly Efficient Constructions over Small Alphabets"
Thursday, December 6, 2018
5:00 p.m.-6:30 p.m.
AVW 2168
For More Information:
Ajaykrishnan Nageswaran
301 405 3661

Communication, Control and Signal Processing Seminar

Synchronization Strings: Highly Efficient Constructions over Small Alphabets

Ke Wu

Synchronization strings were recently introduced by Haeupler and Shahrasbi 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. For all such applications, synchronization strings are desired to be over alphabets that are as small as possible, since a larger alphabet size corresponds to more redundant information added. Haeupler and Shahrasbi showed that for any parameter $\epsilon > 0$, synchronization strings of arbitrary length exist over an alphabet whose size depends only on $\epsilon$. Specifically, Haeupler and Shahrasbi obtained an alphabet size of $O(\epsilon^{-4})$, which left an open question on where the minimal size of such alphabets lies between $O(\epsilon^{-1})$ and $O(\epsilon^{-4})$. In this work, we partially bridge this gap by providing an improved lower bound of $O(\epsilon^{-3/2})$, and an improved upper bound of $O(\epsilon^{-2})$. We also provide fast explicit constructions of synchronization strings over small alphabets.

Further along the lines of previous work on similar combinatorial objects, we study the extremal question of the smallest possible alphabet size over which synchronization strings can exist for some constant $\epsilon < 1$. We show that one can construct $\epsilon$-synchronization strings over alphabets of size four while no such string exists over binary alphabets. This reduces the extremal question to whether synchronization strings exist over ternary alphabets.

This Event is For: Graduate • Undergraduate • Faculty • Post-Docs

Browse Events By Calendar

Calendar Home

« Previous Month    Next Month »

July 2019
1 2 3 4 5 6 w
7 8 9 10 11 12 13 w
14 15 16 17 18 19 20 w
21 22 23 24 25 26 27 w
28 29 30 31 w

Search Events

ISR lecture and seminar series

Distinguished Lecturer Series
Intelligent Automation Inc. Colloquia Series
Microsystems Seminar Series
Lockheed Martin Robotics Seminar Series
Advanced Networks Colloquia Series
Model-Based Systems Engineering Colloquia Series

Submit an event to the ISR calendar Click here

News links

Current news
Search news
News archives