Summary

Understanding the capacity of noisy communication channels, that is, the limit of reliable information transmission over noisy communication channels, and designing efficient codes for such channels are major cornerstones of information and coding theory. Most techniques developed in this area in the last 75 years have been targeted at discrete memoryless channels, which have the property that the i-th received symbol is an independent noisy function of the i-th transmitted symbol only. As a result, sender and receiver are synchronized, greatly simplifying their analysis. The study of such channels has given rise to a rich theory with many important applications beyond their original motivation.

One of the simplest examples is the erasure channel that independently erases each input bit with probability d, replacing it with a "?". For example, if the input is 010101, then a possible output may be 0??1?1. We have known since Shannon's seminal work in 1948 that the capacity of the erasure channel is 1-d. Now, consider the very similar "deletion channel" that independently deletes each input bit with probability d. For example, if the input is 010101, then a possible output may be 011. Now we are no longer sure whether the first output bit corresponds to the first input bit -- we are no longer synchronized.

What is the capacity of the deletion channel as a function of the deletion probability d?

We do not know! This is the centerpiece question of the LESYNCH project. Almost all techniques designed for discrete memoryless channels break down when applied to channels with loss of synchronization. Therefore, studying even the simplest such channels requires developing conceptually new techniques. I expect these techniques to have groundbreaking influence in other areas, like the techniques developed for discrete memoryless channels did. There are several fascinating problems of independent interest that arise along the way towards settling this question. And reflecting on the connection between this question and DNA-based data storage leads to practically relevant and virtually unexplored variants of the basic deletion channel.

This project has two broad, complementing fronts:

• We wish to better understand the fundamental limits of reliable communication (the channel capacity) over channels with deletions, insertions, and other errors that cause loss of synchronization. This includes "multi-trace" channels and non-i.i.d. error models, motivated by DNA-based data storage. We will also explore connections to other interesting information-theoretic problems beyond synchronization errors that we expect will arise along the way.

• We wish to design error-correcting codes for the settings above with good rate and practical encoding and decoding procedures, and possibly other relevant properties. We are also interested in understanding codes correcting adversarial (aka combinatorial) errors.

If you would like to read more about the project's topic, take a look at these surveys:

• A survey of results for deletion channels and related synchronization channels, by Michael Mitzenmacher.

• An overview of capacity results for synchronization channels, by Mahdi Cheraghchi and I.

• Synchronization strings and codes for insertions and deletions -- a survey, by Bernhard Haeupler and Amirbehshad Shahrasbi.