ECCC-Report TR21-079https://eccc.weizmann.ac.il/report/2021/079Comments and Revisions published for TR21-079en-usWed, 09 Jun 2021 19:59:13 +0300
Paper TR21-079
| The zero-rate threshold for adversarial bit-deletions is less than 1/2 |
Venkatesan Guruswami,
Xiaoyu He,
Ray Li
https://eccc.weizmann.ac.il/report/2021/079We 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 going to $0$ asymptotically. Equivalently, we show that there exists absolute constants $A$ and $\delta>0$ such that any set $C\subset\{0,1\}^N$ of $2^{\log^A N}$ binary strings must contain two strings $c$ and $c'$ whose longest common subsequence has length at least $(1/2+\delta)N$. As an immediate corollary, we show that $q$-ary codes tolerating a fraction $1-(1+2\delta)/q$ of adversarial deletions must also have rate approaching $0$.
Our techniques include string regularity arguments and a structural lemma that classifies binary 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.Wed, 09 Jun 2021 19:59:13 +0300https://eccc.weizmann.ac.il/report/2021/079