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:
- Algebraic Geometric Codes (taken by Steve)
- Fast decoding of Reed-Solomon Codes (taken by Swapnoneel)
- Decoding in presence of side information (taken by Jeff)
- Extractors and Codes (taken by JD)
- Linear Programming bound on codes
- Deletion channels
- Arbitrary varying channel
- LP decoding
- Codes in hardness amplification
- Complexity issues in coding theory (taken by Krishna)
- 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.
- 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.
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
By: harmeet on June 4, 2009
at 9:35 am
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.
By: atri on June 4, 2009
at 10:45 pm