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

We prove that there exists an absolute constant δ > 0 such that any binary code C ⊂ 0, 1 N tolerating (1/2 -δ )N adversarial deletions must satisfy |C| 2 poly log N and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating N/2 adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants A and δ > 0 such that any set C ⊂ 0, 1 N of 2 log A N binary strings must contain two strings c and c ′ whose longest common subsequence has length at least (1/2 + δ )N. As an immediate corollary, we show that q-ary codes tolerating a fraction 1 -(1 + 2δ )/q of adversarial deletions must also have rate approaching 0.

Our techniques include string regularity arguments and a structural lemma that classifies binary strings by their oscillation patterns. Leveraging these tools, we find in any large code two strings with similar oscillation patterns, which is exploited to find a long common subsequence.