Theory Seminar

The zero-rate threshold of adversarial bit-deletions is less than 1/2

Ray LiStanford University
(Joint with Purdue. Please follow the Event Website link.)
Error correcting codes protect data from noise. Deletion errors are pervasive, yet codes correcting deletions are poorly understood. I will discuss recent work that answers a basic deletion codes question: Can binary codes of non-vanishing rate correct a worst-case deletion rate approaching 1/2? (1/2 is a natural limit because of a trivial argument) We show that the answer is no: Any binary code correcting a worst-case deletion rate of 0.49…9 must have rate asymptotically approaching zero. This is also a combinatorial result about longest common subsequences: We show that any set with at least 2^{polylog N} length N binary strings must contain two strings c and c’ whose longest common subsequence has length at least 0.50..01N.
I also discuss our techniques, which include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns.

Based on joint work with Venkatesan Guruswami and Xiaoyu He.