期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that there exists an absolute constant 0 such any binary code C01N tolerating (12−)N adversarial deletions must satisfy C2\polylogN and thus have rate asymptotically approaching 0. This is the first constant fraction improvement over the trivial bound that codes tolerating N2 adversarial deletions must have rate going to 0 asymptotically. Equivalently, we show that there exists absolute constants A and 0 such that any set C01N of 2logAN binary strings must contain two strings c and c whose longest common subsequence has length at least (12+)N . As an immediate corollary, we show that q-ary codes tolerating a fraction 1−(1+2)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.
关键词：combinatorial bounds;deletion codes;longest common subsequence;Regularity Lemma;zero-error information theory
