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

Done