摘要 : We prove that there exists an absolute constant $\delta 0$ such that any binary code $C\subset \{0,1\}^{N} \vphantom {_{\int }}$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{ \mathop {\math... 展开 We prove that there exists an absolute constant $\delta 0$ such that any binary code $C\subset \{0,1\}^{N} \vphantom {_{\int }}$ tolerating $(1/2-\delta)N$ adversarial deletions must satisfy $|C|\le 2^{ \mathop {\mathrm {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. 收起