Seminar Details
The Zero Rate Threshold For Adversarial Bit-Deletions is Less Than 1/2
- Start Date: January 26, 2022
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Ray Li - Stanford University
- Event Location: Online Event
- Event Additional Info: <p>Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar. </p> <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar" target="_blank">https://theory.cs.rutgers.edu/theory_seminar</a> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
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.