Introduction to coding theory (CMU, Spr 2010)

May 3, 2010

Wrap up

Filed under: Announcements — Venkat Guruswami @ 6:07 pm

Thanks once again to all of you who took the course and hung in there for the semester! I certainly had a great time with the course, and we covered a lot of ground despite the few Friday classes that had to be cancelled.

I have entered the grades on the electronic web form and I think you should be able to access it soon.

If you have not done so already, please fill in the course evaluation at under Academics. You probably also got an email with instructions on where to fill this out.

There was some request for notes on the 3-query LDCs we covered in the final lecture. I may not be able to write full blown notes, but I’ll try to expand the lecture summary for that post with some details of the construction and analysis when I find time.


April 22, 2010

List-decodability of random linear codes

Filed under: Announcements — Venkat Guruswami @ 9:46 am

In our discussion on random coding arguments to show the existence of list-decodable codes, we showed that a random q-ary code of rate 1-h_q(p)-1/L was (p,L)-list decodable w.h.p. For random linear codes over {\mathbb F}_q, the result (or rather proof) was weaker, and only guaranteed a rate of 1-h_q(p)-1/\log_q(L+1). I had mentioned that this discrepancy in list-size between linear and general codes was recently resolved, showing that a random linear code of rate 1-h_q(p) - O(1/L) is (p,L)-list decodable w.h.p as well.

I’ll speak about this result in the ACO seminar today. The paper can be downloaded here.

March 4, 2010

No class tomorrow (March 5)

Filed under: Announcements — Venkat Guruswami @ 12:36 pm

Continuing the recent theme of one lecture per week, I just learned that there are no classes tomorrow for “mid semester break.” So we won’t have a lecture tomorrow. Have a great spring break and I will see you in lecture on Wednesday, March 17. The problem set will still be due on Mar 19th.

February 23, 2010

Notes for Lecture 10

Filed under: Announcements — Venkat Guruswami @ 2:37 pm

Some notes on Reed-Solomon and BCH codes (in pdf form) are now posted on the course webpage. I’ll post an expanded version including material from tomorrow’s lecture on the blog when it is ready.

February 16, 2010

Regular lecture tomorrow

Filed under: Announcements — Venkat Guruswami @ 4:51 pm

Tomorrow (Feb 17) we will have a regular lecture, and not a special lecture by Madhu Sudan on progress and challenges in coding theory as earlier announced (this is due to weather related travel disruptions). We might have the special lecture for Friday’s class (Feb 19); I will announce later if that is the case.

February 13, 2010

Upcoming lectures

Filed under: Announcements — Venkat Guruswami @ 9:17 am

Two important announcements about the lectures during the coming two weeks:

  1. Madhu Sudan, who will be visiting CMU this week, has kindly agreed to give a guest lecture in our course on Wednesday, Feb 17th. The topic will roughly be a survey on some progress and challenges ahead in coding theory. It should be very useful and informative for the course, so please attend!
  2. There will be no class on Friday, Feb 26, in view of the CSD open house. Students are encouraged to participate in the afternoon poster sessions or otherwise be involved in the visit day activities instead.

February 10, 2010

No class today

Filed under: Announcements — Venkat Guruswami @ 12:21 pm

Since some students explicitly asked me, I wanted to make it clear that we do not have a lecture today in view of CMU canceling its classes for the day.

In light of this disruption over the past few days, you can take two extra days for the problem set if you wish, and turn it in by Feb 19 (which will be a firm deadline).

January 5, 2010

Welcome and Readme

Filed under: Announcements — Venkat Guruswami @ 4:03 pm

This is the class blog for CMU’s Spring 2010 graduate CS course 15-859V: Introduction to Coding Theory. The course instructor is Venkatesan Guruswami. There is no TA.

The course homepage is, where you can find basic information about the course, the expected workload, and some pointers to reference material. The course webpage will be mostly static, except perhaps for postings of the problem sets (which will also be announced here).

There is no class mailing list, so please check this blog regularly, or add it to your RSS feed. We will use the blog to post announcements (e.g., “There is a correction to question 3 on the problem set…”), lecture summaries (and hopefully, with cooperation from students taking the course for credit, also some notes), corrigenda and updates, problem set hints, etc. The blog may also occasionally include small sidenotes or supplementary technical material not covered in lectures.

Another important feature of the blog is to let you ask questions or make comments about the subject material. There will be a short lecture summary post for each lecture, and I encourage you to use the “Comments” feature to post questions or comments.

Create a free website or blog at