# Introduction to coding theory (CMU, Spr 2010)

## April 22, 2010

### List-decodability of random linear codes

Filed under: Announcements — Venkat Guruswami @ 9:46 am

In our discussion on random coding arguments to show the existence of list-decodable codes, we showed that a random $q$-ary code of rate $1-h_q(p)-1/L$ was $(p,L)$-list decodable w.h.p. For random linear codes over ${\mathbb F}_q$, the result (or rather proof) was weaker, and only guaranteed a rate of $1-h_q(p)-1/\log_q(L+1)$. I had mentioned that this discrepancy in list-size between linear and general codes was recently resolved, showing that a random linear code of rate $1-h_q(p) - O(1/L)$ is $(p,L)$-list decodable w.h.p as well.