Alladi Ramakrishnan Hall

Long common subsequences between bitstrings and the zero-rate threshold of binary deletion codes

Venkat Guruswami

EECS, Berkeley University

What's the largest fraction, say p*, of (worst-case) bit deletions
that can be corrected with a binary code of non-vanishing rate? A
trivial limit is that p* is at most 1/2, as the channel can delete 1/2
of the n transmitted bits to ensure the receiver gets a string of n/2
repeated 0's or 1's. It remained a longstanding open problem if this
simple upper bound can be improved.

We prove that there exists an absolute constant delta > 0 such any
binary code C that can correct (1/2-delta)n bit-deletions must have at
most quasi-polynomially many codewords, and thus have rate going to 0
asymptotically. In other words, the zero-rate threshold p* of
worst-case bit-deletions is bounded away from 1/2. Equivalently, we
show that there exists absolute constants A and delta > 0 such that
any subset C of exp(log^A n) n-bit strings must contain two strings
whose longest common subsequence has length at least (1/2+delta)n.

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.

Joint work with Xiaoyu He and Ray Li.