I just submitted the final grades. You will receive an individual email with more details in a few days.

Again, I had a great time teaching the course: thanks for being a great class!

Since some of you seem to need some more time for the notes, I am extending the deadline for scribed notes to 11:59pm EST, Dec 13. However, note that the earlier you submit the notes, you get more points on the timeliness part of the grade.

The deadline for the project report is still 8am EST, Dec 11.

In today’s lecture we (barely) finished decoding of folded Reed-Solomon code and showed that certain rate folded RS codes can be list decoded up to a fraction of errors. Unfortunately, due to lack of time, I had to skip some proofs and derivations (for example how to choose the values of the parameters and ). Take a look at this chapter in my thesis for details.

A semester is too short a time to do justice to the numerous interesting topics in coding theory. A good place to look for such topics are the suggested project topics. Let me mention some of these topics in no particular order (that we either mentioned in passing in the class or did not mention them at all).

• Irregular LDPC codes. These codes can provably achieve the capacity of the . They also experimentally seem to achieve the capacity of the . The big advantage for these codes are the linear time encoding and decoding algorithms (the dependence on , the distance from capacity, is also some small polynomial). For more details see this survey by Venkat Guruswami.
• Expander codes. These are certain explicit regular LDPC codes whose factor graphs are some special graphs called expanders. These give us the only linear time encodable and decodable binary codes (in the worst-case noise model). For more details, see this survey by Venkat Guruswami.
• Algebraic Geometry codes. These codes beat the Gilbert-Varshamov bound for alphabets . See my post on the corresponding project topic for more pointers.
• Linear Programming bounds. The best known lower bound on the rate vs. distance question are achieved via the so called Linear Programming bound. See my post on the project topic for more pointers.
• Convolutional Codes. All the codes that we covered in class were block codes. That is, the block length of such codes are fixed. However, there are many applications where having a fixed block length might be too wasteful. Convolutional codes allow for variable block lengths and “on the fly” encoding and decoding.
• Applications in Complexity theory. There are numerous applications of coding theory in theoretical computer science and in partiuclar, complexity theory (and cryptography). We only had time to cover one such application: secret sharing. However, some of the biggest advances in coding theory (for example the PCP theorem) have used tools from coding theory. For more details, see this survey by Luca Trevisan or the my blog posts on the following project topics: codeword testing, extractors, locally decodable codes, and hardness amplification. For applications of list decoding in complexity theory see this survey by Madhu Sudan.

I had fun teaching this course: hopefully you guys had some fun too!

ps: don’t forget the project reports and scribed notes

In today’s lecture, we saw how to decode folded RS codes of rate up to fraction of errors. For suitable choice of parameters, one can correct fraction of errors with rate (I think the stated an incorrect bound on the rate in class). We still need to prove the following lemmas

• There exists an irreducible polynomial of degree such that for any polynomial of degree at most , the following is true: , where is the generator of the field .
• Given an polynomial that needs to be output in the second step of the list decoding algorithm, we have , where and are thought of as elements of . Recall that was defined as , where (with coefficients from ) is just . Finally, recall is the largest factor of from step 1 of the algorithm that is not divisible by .

In the next (and last!) lecture, we will quickly prove the above two lemmas. Then we will see how a small change to the algorithm allows us to decode from fraction of errors in polynomial time (for constant ). If we have more time, we will either briefly cover list decoding of binary codes and/or topics that we did not cover in any detail in this class.

I’ll like to take you guys out for lunch at noon on Wednesday. Please use the comments section of this entry to let me know if you can make it.

In case you sent me scribes of some lecture notes and I did not acknowldge the receipt, could you please re-send it (and also put in a comment for this entry?)

Nathan and Sandipan: you do not need to respond as I know I did not receive emails that you sent.

In today’s lecture we finished talking about list recovery and soft decoding of RS codes. We then defined folded RS codes and saw an intuition for why these new codes might help push the fraction of errors beyond . I might have gone a bit fast on some portions of the lecture. Please use the comments section if you have any questions.

Next lecture, we will present a list decoding algorithm for folded RS codes and delve into its analysis. We will be using a bit of extension fields, so this is a good time to brush up your knowledge about them and irreducible polynomials. Actually, we will just use the fact that , where is an irreducible polynomial of degree is the field . The notation denotes all polynomials with coefficients from modulo the polynomial .

In today’s lecture we finished proving the two lemmas that were stated in the last lecture. We also saw the definition of soft decoding. In the beginning of the next lecture, we will quickly see how one can generalize the GS algorithm to do soft decoding of RS codes. Then we will move on to some recent algorithmic results in list decoding.

I have finished revising the notes for lectures 15, 20 and 21. Thanks to Than, Kanke and Michel for scribing!

In today’s lecture, we first saw Sudan’s list decoding algorithm and proved that it could correct fraction of errors for rate Reed-Solomon codes. We then looked at the Guruswami-Sudan list decoder and proved it could correct fraction of errors (modulo a couple of lemmas).

Next lecture, we will prove the lemmas mentioned above. Then we will talk about some implications for a couple of generalization of the list decoding problem. If we have time, we will start talking about some recent results in list decoding.