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

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

Based on joint work with Venkatesan Guruswami and Xiaoyu He.