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

SEMINARS, CMSA EVENTS

View Calendar
April 27, 2022 9:30 am - 10:30 am
via Zoom Video Conferencing
Speaker:

Venkatesan Guruswami - UC Berkeley


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.


For information on how to join, please see:  https://cmsa.fas.harvard.edu/seminars-and-colloquium/