Abstract

Abstract: I will describe efficient codes for synchronization from insertions and deletions. As an example, consider remotely located users who independently edit copies of a large file (e.g. video or text), where the editing may involve deleting certain parts of the file, and inserting new data in other parts. The users then want to synchronize their versions with minimal exchange of information (in terms of both the communication rate and the number of interactive rounds of communication). This is an important problem that has applications in online editing, file sharing, and data storage in the cloud.

We focus on the case where the number of edits small compared to the file-size, and describe an interactive synchronization algorithm which is computationally simple and has near-optimal communication rate. The algorithm is based on a class of single-deletion correcting channel codes due to Varshamov and Tenengolts (VT codes).