Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions

Understand

We present many new results related to reliable (interactive) communication over insertion-deletion channels.

• Synchronization errors, such as insertions and deletions, strictly generalize the usual symbol corruption errors and are much harder to protect against.
• We show how to hide the complications of synchronization errors in many applications by introducing very general channel simulations which efficiently transform an insertion-deletion channel into a regular symbol corruption channel with an error rate larger by a constant factor and a slightly smaller alphabet.
• We generalize synchronization string based methods which were recently introduced as a tool to design essentially optimal error correcting codes for insertion-deletion channels.