文章基本信息

标题：On the List-Decodability of Random Linear Codes
本地全文：下载
作者：Venkatesan Guruswami ; Johan Hastad ; Swastik Kopparty 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：For every fixed finite field \Fq, p(01−1q) and 0, we prove that with high probability a random subspace C of \Fnq of dimension (1−Hq(p)−)n has the property that every Hamming ball of radius pn has at most O(1) codewords. This answers a basic open question concerning the list-decodability of linear codes, showing that a list size of O(1) suffices to have rate within of the ``capacity'' 1−Hq(p). This matches up to constant factors the list-size achieved by general random codes, and gives an exponential improvement over the best previously known list-size bound of qO(1) . The main technical ingredient in our proof is a strong upper bound on the probability that random vectors chosen from a Hamming ball centered at the origin have too many (more than ()) vectors from their linear span also belong to the ball.
关键词：list-decoding, random linear codes, Sauer-Shelah lemma