Yesterday, Jesse defined the notion of the distance of a code and mentioned some its consequences. The material was from Sec 1.4 in the book.

On Monday, we studied the error correctability (and detectability) of the parity and repetition codes. We also looked at some ways of modeling noise. The material was from Sec 1.3 in the book.

A reminder that tomorrow, Jesse will present the lecture. He will talk about the distance parameter of a code.

In today’s lecture we informally stated the big question that will motivate most of what we do this semester and then started with basic definition with the goal of formalizing the big question. The material is from (part of) Sec 1.1, Sec 1.2 and (part of) Sec 1.3

In today’s lecture, we mostly we over the syllabus.

We then briefly talked about some practical motivation of codes. The slides for today’s lecture have been uploaded.

Also don’t forget the feedback form!

Please fill in this anonymous feedback form so that I have an idea of the background knowledge that this class has. It’ll help me tailor my lectures accordingly.

Further, at any point of time in the semester if you have a comment, feel free to use the anonymous feedback form via the link on the right panel.

This is the course blog for the Spring 2012 offering of CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications at CSE@UB.

If you are a student in the class, it is your responsibility to keep up to date with the blog posts here. Consider subscribing to the RSS feed (click the first button on the right panel). Or sign up for email notifications (button the the right panel).

This should be a fun course for everyone involved and I am looking forward to it!

ps: those who signed up for the blog last year, here is some information in case you want to unsubscribe. (The post is on the blog for another course but the information there will work for this blog.)

I just submitted the grades for the course.

I uploaded your letter grades as well the scores of the items that I had not graded earlier to UBLearns. I used the following split to calculate the final grade:

• Proof-Reading+Scribing: 40%
• Homeworks: 25%
• Wikipedia: 35%

It was great to have y’all in the class: hope you guys had fun in the course! (I had fun teaching it.)

On May 2nd, we saw how we can use list decoding to problem of approximating NP-witnesses in computational complexity.

I did not get time to talk about the many important topics that we did not get to cover in this course. Here is an old blog post with a list of topics that we did not get to study in this course.

On Friday, we finished proving that Guruswami’s list decoding algorithm for FRS codes can achieve list decoding capacity in polynomial time. Finally, we started talking about approximating NP-witness, which we will finish in our last lecture on Monday.

In Wednesday’s lecture, we saw how to get close to the list decoding capacity result for FRS codes. We did the entire proof modulo proving that Step 2 does not output too many polynomials. We’ll complete this last step today and then move on to a complexity application of complexity theory.