# 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 my.cmu.edu 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.

## 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).