CSE 545, Error Correcting Codes: Combinatorics, Algorithms and Applications


Atri Rudra
(716) 645-3180 x 117
123 Bell Hall
Office Hours:
Mondays, 1:00-1:50pm (or by appointment)

Class Meetings

Monday, Wednesday, Friday. 2:00-2:50pm
110 Baldy Hall

Fall 2007 offering

Course Announcement

Course Syllabus

Course Blog

We will be using a blog for the course in lieu of a course newsgroup. All announcements will be made on the blog. If you are attending the course, you must check the blog regularly (and consider subscribing to the RSS feed).



N.B. The notes marked Draft of notes have not been reviewed by me at all. I hope to get them polished by summer 2010. --Atri

Use this style file for scribing notes. To get you started, here is a sample TeX file. (Both of these have been borrowed from Venkat Guruswami's style file from his coding theory course.)


Optional Reading

Course Pre-requisites

There is no specific course pre-requisite for this course. However, some "mathematical maturity" will be essential. In particular, comfort with basics of linear algebra (vector spaces, basis, dual spaces); finite fields, field extensions and polynomials over finite fields; elementary probability; analysis of algorithms; and (some exposure to) computational complexity will be useful. Some of these topics (for example finite fields) can be learned on a need to know basis as the course progresses. Email the instructor if you have any questions on the pre-requisites.

Reference material

We will not follow any particular textbook. Instead, we will use lecture notes from the previous fall 2007 offering of the course (as CSE 510C). Note: Unfortunately, not all the lecture notes are polished (i.e. those marked as draft): I plan to polish them before the relevant lecture this semester.

Another good resource is the excellent set of lecture notes for Madhu Sudan's coding theory course at MIT: Notes from 2001, 2002, 2004 and 2008. You might also want to check out the notes from Venkat Guruswami's coding theory course.

The basic material on codes that we will discuss in initial lectures can be found in one of many textbooks (some of the standard ones are listed below), but the recent algorithmic developments and applications in computer science are not covered in any of these: Though we won't cover much information theory in this course, if you are interested to know more on topics such as entropy, capacity theorems, source coding, etc., there is the classic information theory text


The workload will be moderate: there will be no exams. The following will be the major components:

Grading Policy

Here is a rough split of grades:

Academic Honesty

I have zero tolerance for cheating and will follow the CSE Department Policies on Academic Integrity.


The material in this webpage is supported in part by the National Science Foundation under CAREER grant CCF-0844796. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).