Title: Synchronization Strings: Channel Simulations and Interactive Coding for Insertions and Deletions,
Abstract: 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. Our channel simulations depend on the
fact that, at the cost of increasing the error rate by a constant factor,
synchronization strings can be decoded in a streaming manner that preserves
linearity of time. We also provide a lower bound showing that this constant
factor cannot be improved to $1+\epsilon$, in contrast to what is achievable
for error correcting codes. Our channel simulations drastically generalize the
applicability of synchronization strings.
We provide new interactive coding schemes which simulate any interactive
two-party protocol over an insertion-deletion channel. Our results improve over
the interactive coding schemes of Braverman et al. [TransInf 2017] and Sherstov
and Wu [FOCS 2017], which achieve a small constant rate and require exponential
time computations, with respect to computational and communication
complexities. We provide the first computationally efficient interactive coding
schemes for synchronization errors, the first coding scheme with a rate
approaching one for small noise rates, and also the first coding scheme that
works over arbitrarily small alphabet sizes.