Speaker: Venkatesan Guruswami, UC Berkeley

Title: Long common subsequences between bit-strings and the zero-rate threshold of deletion-correcting codes

Abstract: Suppose we transmit n bits on a noisy channel that deletes some fraction of the bits arbitrarily. What’s the supremum p* of deletion fractions that can be corrected with a binary code of non-vanishing rate? Evidently p* is at most 1/2 as the adversary can delete all occurrences of the minority bit. It was unknown whether this simple upper bound could be improved, or one could in fact correct deletion fractions approaching 1/2.
We show that there exist absolute constants A and delta > 0 such that any subset of n-bit strings of size exp((log n)^A) must contain two strings with a common subsequence of length (1/2+delta)n. This immediately implies that the zero-rate threshold p* of worst-case bit deletions is bounded away from 1/2.

Our techniques include string regularity arguments and a structural lemma that classifies bit-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.

This is joint work with Xiaoyu He and Ray Li.