Theory Seminar
— 12:00pm
Location:
McWilliams Classroom 4303
-
Gates Hillman Centers
Speaker:
XIN LI
,
Assistant Professor
http://www.cs.jhu.edu/~lixints/
Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors
We study two basic problems regarding edit errors, i.e. document exchange and error correcting codes for edit errors (insdel codes). For message length n and edit error upper bound k, it is known that in both problems the optimal sketch size or the optimal number of redundant bits is \Theta(k log(n/k)). However, previous known constructions are far from achieving these bounds.
We significantly improve previous results on both problems. For document exchange, we give an efficient deterministic protocol with sketch size O(k log^2(n/k)). This significantly improves the previous best known deterministic protocol, which has sketch size O(k^2+k log^2 n) (Belazzougui15). For binary insdel codes, we obtain the following results:
- An explicit binary insdel code which encodes an n-bit message against k errors with redundancy O(k log^2(n/k)). In particular this implies an explicit family of binary insdel codes that can correct \epsilon fraction of insertions and deletions with rate 1−O(\epsilon log^2(1/\epsilon))=1−\tilde{O}(\epsilon).
- An explicit binary insdel code which encodes an n-bit message against k errors with redundancy O(k log n). This is the first explicit construction of binary insdel codes that has optimal redundancy for a wide range of error parameters k, and this brings our understanding of binary insdel codes much closer to that of standard binary error correcting codes.
In obtaining our results we introduce the notion of \emph{\epsilon-self matching hash functions} and \emph{\epsilon-synchronization hash functions}. We believe our techniques can have further applications in the literature.
Joint work with Kuan Cheng, Zhengzhong Jin, and Ke Wu.
Faculty Host: Venkatesan Guruswami
Event Website:
http://theory.cs.cmu.edu/seminars/
For More Information:
venkatg@cs.cmu.edu