期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Recently Efremenko showed locally-decodable codes of sub-exponential
length. That result showed that these codes can handle up to
31 fraction of errors. In this paper we show that the
same codes can be locally unique-decoded from error rate
\half− for any 0 and locally list-decoded from
error rate 1− for any 0, with only a constant
number of queries and a constant alphabet size. This gives the first
sub-exponential codes that can be locally list-decoded with a
constant number of queries
