Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LIST SIZE:
Reports tagged with List size:
TR09-013 | 4th February 2009
Atri Rudra

#### Limits to List Decoding Random Codes

It has been known since [Zyablov and Pinsker 1982] that a random $q$-ary code of rate $1-H_q(\rho)-\eps$ (where $0<\rho<1-1/q$, $\eps>0$ and $H_q(\cdot)$ is the $q$-ary entropy function) with high probability is a $(\rho,1/\eps)$-list decodable code. (That is, every Hamming ball of radius at most $\rho n$ has at most $1/\eps$ ... more >>>

ISSN 1433-8092 | Imprint