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.

I’ll speak about this result in the ACO seminar today. The paper can be downloaded here.


Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

Create a free website or blog at

%d bloggers like this: