Posted by: atri | December 23, 2007

Grades submitted

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!

Posted by: atri | December 10, 2007

Deadline extension for scribed notes

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.

Posted by: atri | December 7, 2007

Lecture 42: Achieving List Decoding Capacity

In today’s lecture we (barely) finished decoding of folded Reed-Solomon code and showed that certain rate R folded RS codes can be list decoded up to a 1-R-\epsilon 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 m,s and r). 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 BEC_{\alpha}. They also experimentally seem to achieve the capacity of the BSC_p. The big advantage for these codes are the linear time encoding and decoding algorithms (the dependence on \epsilon, 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 q\ge 49. 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 :-)

Posted by: atri | December 5, 2007

Lecture 41:Parvaresh Vardy Decoder

In today’s lecture, we saw how to decode folded RS codes of rate R up to 1-\sqrt[m+1]{(mR)^m} fraction of errors. For suitable choice of parameters, one can correct 1-\epsilon fraction of errors with rate \Omega(\epsilon/\log(1/\epsilon)) (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 E(X) of degree q-1 such that for any polynomial f(X) of degree at most q-2, the following is true: f(X)^q\equiv f(\gamma X)\mod(E(X)), where \gamma is the generator of the field \mathbb{F}_q.
  • Given an polynomial f(X) that needs to be output in the second step of the list decoding algorithm, we have T(f(X),f(\gamma X))\equiv 0, where f(X) and f(\gamma X) are thought of as elements of \mathbb{F}_q[X]/E(X)\equiv \mathbb{F}_{q^{q-1}}. Recall that T(Y,Z) was defined as T_0(Y,Z)\mod(E(X)), where T_0(Y,Z) (with coefficients from \mathbb{F}_q[X]) is just Q_0(X,Y,Z). Finally, recall Q_0(X,Y,Z) is the largest factor of Q(X,Y,Z) from step 1 of the algorithm that is not divisible by E(X).

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 1-R-\epsilon fraction of errors in polynomial time (for constant \epsilon>0). 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.

Posted by: atri | December 3, 2007

Lunch on Wednesday

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.

Posted by: atri | December 3, 2007

Missing lecture notes

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.

Posted by: atri | December 3, 2007

Lecture 40: Folded Reed-Solomon Codes

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 1-\sqrt{R}. 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 \mathbb{F}_q[X]/E(X), where E(X) is an irreducible polynomial of degree k is the field \mathbb{F}_{q^k}. The notation \mathbb{F}_q[X]/E(X) denotes all polynomials with coefficients from \mathbb{F}_q modulo the polynomial E(X).

Posted by: atri | November 30, 2007

Lecture 39: GS Decoder Wrap-up

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.

Posted by: atri | November 29, 2007

Notes for Lectures 15, 20 and 21

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

Posted by: atri | November 28, 2007

Lecture 38: Guruswami-Sudan List Decoder

In today’s lecture, we first saw Sudan’s list decoding algorithm and proved that it could correct 1-\sqrt{2R} fraction of errors for rate R Reed-Solomon codes. We then looked at the Guruswami-Sudan list decoder and proved it could correct 1-\sqrt{R} 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.

Older Posts »

Categories