Interactive Codes for Synchronization
Speaker: Ramji Venkataramanan, Yale University
Series: Topical Seminars
Location:
Engineering Quadrangle B205
Date/Time: Thursday, March 3, 2011, 4:30 p.m.
- 5:30 p.m.
Abstract:
In this talk, 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). Time permitting, I will also discuss the case where the number of edits is large, and obtain fundamental limits on the optimal communication rate.
This talk is based on joint work with Hao Zhang, Kannan Ramchandran, and Sekhar Tatikonda.
Biography:
Ramji Venkataramanan received the B.Tech degree from the Indian Institute of Technology, and M.S and Ph.D degrees in Electrical Engineering from the University of Michigan, Ann Arbor. He was a postdoctoral researcher at Stanford University from December 2008 to August 2010, and is now at Yale University. His research interests include information theory, coding, network algorithms, and stochastic network theory.
Website: http://pantheon.yale.edu/~rv99/
