Thursday, October 20, 2022 3:00 PM
Xiaoyu He (Princeton University)

Deletion channels, introduced by Levenshtein in the 60's, are noisy channels that delete bits from the input. A (binary) k-deletion code of length n is a set C of binary strings of length n capable of correcting k such errors, i.e. satisfying the property that no pair of elements of C shares a common subsequence of length at least n-k. Let D(n, k) be the size of the largest k-deletion code of length n. Two central problems are to determine (a) the order of D(n, k) for constant k, and (b) the supremum of all 0<p<1 such that D(n, pn) grows exponentially in n (the so-called "positive-rate threshold"). In this talk, we establish the first nontrivial lower bound for problem (a) when k > 1, improving the "greedy" lower bound for D(n,k) by a logarithmic factor. We also prove the first nontrivial upper bound for problem (b), showing that D(n,pn) = 2^o(n) for p > 1/2 - 10^{-60}. The proofs use a variety of techniques from extremal combinatorics including probabilistic methods and regularity.

Based on joint works with Noga Alon, Gabriela Bourla, Ben Graham, Venkatesan Guruswami, Noah Kravitz, and Ray Li.