All reports by Author Xiaoyu He:

__
TR21-079
| 9th June 2021
__

Venkatesan Guruswami, Xiaoyu He, Ray Li#### The zero-rate threshold for adversarial bit-deletions is less than 1/2

Venkatesan Guruswami, Xiaoyu He, Ray Li

We prove that there exists an absolute constant $\delta>0$ such any binary code $C\subset\{0,1\}^N$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{\poly\log N}$ and thus have rate asymptotically approaching $0$. This is the first constant fraction improvement over the trivial bound that codes tolerating $N/2$ adversarial deletions must have rate ... more >>>