Lower Bounds for all List-Decodable Deletion Codes

Andrew D. Lin

A length-$n$ binary $k$-deletion code is a set of binary strings such that if we delete any $k$ bits of a string, leaving a length-$(n-k)$ binary string, we can uniquely recover th…