Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with random linear codes:
TR10-003 | 6th January 2010
Venkatesan Guruswami, Johan HÃ¥stad, Swastik Kopparty

On the List-Decodability of Random Linear Codes

For every fixed finite field $\F_q$, $p \in (0,1-1/q)$ and $\varepsilon >
0$, we prove that with high probability a random subspace $C$ of
$\F_q^n$ of dimension $(1-H_q(p)-\varepsilon)n$ has the
property that every Hamming ball of radius $pn$ has at most
$O(1/\varepsilon)$ codewords.

This ... more >>>

TR21-139 | 24th September 2021
Venkatesan Guruswami, Jonathan Mosheiff

Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity

We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the ... more >>>

ISSN 1433-8092 | Imprint