« The Zero Rate Threshold For Adversarial Bit-Deletions is Less Than 1/2
The Zero Rate Threshold For Adversarial Bit-Deletions is Less Than 1/2
January 26, 2022, 11:00 AM - 12:00 PM
Location:
Online Event
Ray Li, Stanford University
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 an extremely basic deletion codes question: Can binary codes of (asymptotically) positive rate correct a worst-case deletion fraction approaching 1/2? (A trivial argument shows deletion fraction ≥1/2 is not correctable) We show that the answer is no: No positive rate binary codes can correct a worst-case deletion fraction of 0.49…9. 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 distinct 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, very roughly analogous to a Fourier transform, that classifies binary strings by their oscillation patterns.
Based on joint work with Venkatesan Guruswami and Xiaoyu He.
Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.