Interactive Codes for File Synchronization

Add to your list(s) Download to your calendar using vCal

• Ramji Venkataramanan
• Wednesday 12 June 2013, 14:30-15:30
• SigProC seminar room (3rd floor of Dept. of Engineering).

If you have a question about this talk, please contact Prof. Ramji Venkataramanan.

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).

This talk is part of the Communications Research Group Seminar series.

This talk is included in these lists:

• Communications Research Group Seminar
• Information Engineering Division seminar list
• SigProC seminar room (3rd floor of Dept. of Engineering)

Note that ex-directory lists are not shown.