Optimally resilient codes for list-decoding from insertions and deletions

We present a construction of subspace codes along with an efficient algorithm for list decoding from both insertions and deletions, handling an information-theoretically maximum fraction of these with polynomially small rate. Our construction is based ...

Wachter-Zeh (IEEE Trans Inf Theory 59(11):7268–7276, 2013), and later together with Raviv (IEEE Trans Inf Theory 62(4):1605–1615, 2016), proved that Gabidulin codes cannot be efficiently list decoded for any radius $\tau$, providing that $\tau$ is large ...${\mathbb{}}_{{}^{}}$

This paper studies the cardinality of codes correcting insertions and deletions. We give improved upper and lower bounds on code size. Our upper bound is obtained by utilizing the asymmetric property of list decoding for insertions and deletions ...