The project reports are due on Tuesday, Dec 11 by 8am (the deadline for the scribed notes is midnight Dec 11). This is a hard deadline.

Here are some thoughts on my expectations for the project reports (in no particular order):

• I do expect to see proofs in your report. However, the proofs should not be produced verbatim from the papers that you are surveying. Your contribution will be to give the reader the key ideas/intuition in the proofs. Of course it will not be possible for you to give detailed proofs for every result that you state. It is OK to just give the statement of some results: for example, proofs that are just routine calculations. Basically, you are expected to prove (or at least give a proofs sketch) of the important lemmas/theorems that you will mention in your report.
• I am expecting a report of around 20 pages. This number is not a hard number. A report of around 18 pages is fine. Try to keep your report under 30ish pages if possible. Do not try to add material just for the sake of paper count: a shorter coherent report will be graded higher than a longer rambling report.
• You do not need to prove/expand on results we have covered in class unless a detailed understanding of the result is necessary for the rest of your report to make sense.
• The target audience for your report is a person who is comfortable with math (and may have some exposure to basic coding theory). So make sure that your report is accessible to such an audience. Among other things make sure that you motivate the general problem that you are considering well enough. If the reader is not convinced that the problem is interesting/important, the rest of your survey will be useless. Some part of your grade will depend on how accessible your report is to a general audience.
• Please be precise in notation/definition. In particular, define any new term that you will be using (having a short description of the basic notions of codes would helpful for a reader who is not familiar with the coding notions).

If you have any comments/questions, feel free to use the comments section of this post.

In today’s lecture we saw our first non-trivial list decoding algorithm. We saw how to correct fraction of errors for Reed-Solomon codes of rate . This gives an improvement over the unqiue decoding regime of for rates . In the next lecture, we will see another algorithm that can correct up to fraction of errors. Then we will see an algorithm that achives the Johnson bound.

In class today I mentioned that factoring of bivariate polynomials can be done in polynomial. In fact the following three independent work gave efficient algorithms to factor polynomials over constant many variables:

• Dima Grigoriev, Polynomial factoring over a finite field and solving systems of algebraic equations. [English translation in J. of Soviet Math. 1986]
• Erich Kaltofen, Polynomial-time reductions from multivariate to bi- and univariate integral polynomial factorization. [SICOMP 1985]
• Arjen K. Lenstra, Factoring Multivariate Polynomials over Finite Fields. [JCSS 1985]

See you guys in class on Monday.

In today’s lecture we saw the Peeling decoder, which is a linear time implementation of the message passing decoding algorithm that we have seen so far. We then saw a very high level overview of irregular LDPC codes and expander codes.

In the next lecture, we will start with algorithms for list decoding.

In today’s lecture we computed the threshold such that the iterative message passing algorithm has exponentially small decoding error probability for for every . Michel asked what happens when . In this case, it can be shown that even in the limit (that is, when the number of rounds is infinite) the probability of an erasure being passed on an edge is strictly bounded away from zero. In other words, the decoding algorithm is going to have a constant decoding error probability irrespective of the number of iterations. See Guruswami’s survey for a formal proof.

Next lecture, we will see how the decoder can be implemented in linear time and (at a very very high level) why irregular LDPC codes can have a greater threshold than regular LDPC codes (such codes achieve the capacity of ). We will then move on to algorithms for list decoding.

The final revised versions of the scribed notes for lecture 13, 14, and 24 are now online. Thanks to Than and Yang for scribing the notes!

Drafts of the notes for the following lectures are also online (some of which have been updated once): 15, 17, 20, 21, 27 and 29.

In today’s lecture we saw the full description of an iterative message passing algorithm for . We then proved the crucial claim that the random variables corresponding to messages received by a node in the factor graph (in any round of the decoding algorithm) are independent.

Next lecture, we will continue with the analysis of the algorithm.

We are getting to the end of the semester and we are one lecture short of everyone having an even scribing load. First let me spell out the schedule for scribing duties in the “current cycle”:

• Wed, Nov14 : Than
• Fri, Nov16 : Sandipan
• Mon, Nov 19 : Nathan

If any of you cannot make it in your slot above, please talk to the person scheduled next to you and try and switch your slots (and let me know if you do so).

After this there are 6 lectures left. This is what I propose to do: The first three lectures (on Nov. 26, 28 and 30) will be scribed by a group of 3 people while the last three lectures (on Dec 3, 5 and 7) will be scribed by a group of 4 people. The latter group will have less to scribe but will also have less time to finish their scribing duties. Use the comments section to pick which group you want to be in (Than will be in the first group as she has some travel in early december)– first come first serve. If I do not hear back from you by Friday, I’ll form the groups arbitrarily.

Update (Nov 13) The first group is now fixed: Than, Michael and Kanke will scribe the lectures on Nov. 26, 28 and 30 (by default in that order: however, feel free to swap slots among yourselves)

I expect all scribed notes to be turned in by Dec 11, 2007.

In today’s lecture, we started with the definition and motivation for Low-Density Parity-Check codes, which were first studied in Gallager remarkable Ph.D. thesis. We then looked at the iterative message passing algorithm for the .

Next lecture, we will continue with the analysis of the decoding algorithm.

Here is a link to the survey by Guruswami that I mentioned in the class.

In today’s lecture, we finished Thommesen’s proof.

Next lecture, we will switch gears a bit and start with Gallager’s work on LDPC codes.