Posted by: atri | January 29, 2009

Paper list

Finally below is the promised list of papers you can choose from. Please let me know as soon as you pick your paper so that I can make a note of it here and everyone knows that the paper/topic is chosen.  Instead of listing individual papers, I’ll mostly list topics and give a pointer to the relevant blog entry from fall 07, which will have a list of relevant papers. Note: All the presentations will be individual ones and only one person can present form each “topic” below.  Also please note that for some of topics (especially those related to list decoding), we will cover some of the required background material much later in the course. If you have have any questions, feel free to use the comments section.

Ok, so here it goes:

  1. Algebraic Geometric Codes (taken by Steve)
  2. Fast  decoding of Reed-Solomon Codes   (taken by Swapnoneel)
  3. Decoding in presence of side information (taken by Jeff)
  4. Extractors and Codes (taken by JD)
  5. Linear Programming bound on codes
  6. Deletion channels
  7. Arbitrary varying channel
  8. LP decoding
  9. Codes in hardness amplification
  10. Complexity issues in coding theory (taken by Krishna)
  11. We will study the Guruswami-Sudan algorithm for list decoding Reed-Solomon codes. Till date this algorithm has not been improved for Reed-Solomon codes. There have been some recent work which  indicate that the Guruswami-Sudan algorithm might be the best possible. Here are four papers in this vein: Guruswami-Rudra05 (this showed that GS is optimal for list recovering Reed-Solomon codes), Ben-Sasson-Kopparty-Radhakrishnan06 (this work showed that for polynomially small rate, GS is almost optimal for list decoding RS codes: their main idea is surprsingly simple yet very effective),  Cheng-Wan04 (this work showed a connection between list decoding Reed-Solomon codes and the discrete-log problem). There has been a recent followup to Cheng-Wan04 by the same authors.
  12. Guruswami-Rudra08 (this work shows that there exists concatenated codes over fixed alphabets that have optimal list decodability).

You are more than welcome to choose your own paper but please get my approval first.

Warning: Some of the paper above have some very heavy-duty math. So start your decision process early!

Update (Mar 25): Willmert will be talking about association schemes as they relate to codes.



  1. I am not a student of this university, but i am trying to go through these topics.
    Can i get any help from your side

  2. Hi Harmeet,

    Unfortunately, I cannot offer you much help outside of what is already there on the blog and the lecture notes. If any of the explanations in the lecture notes are not clear, let me know and I’ll try to update the notes to make them more accessible. However, can’t promise you a (speedy) response.

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s


%d bloggers like this: