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).
This will give an overview of the topics we will cover in the class. Comments are welcome.
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:
Introduction to Coding Theory, by J. H. van Lint, GTM 86.
The Theory of Error Correcting Codes, by F. J. MacWilliams and N. J. A. Sloane, North-Holland, Amsterdam.
Algebraic codes for data transmission. by Richard E. Blahut.
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
Elements of Information Theory, Thomas M. Cover and Joy A. Thomas,
Wiley Series in Telecommunications, 1991.
Workload
The workload will be moderate: there will be no exams. The following
will be the major components:
Scribing notes. A few lectures will cover topics that were not
covered in the last offering: these lectures will need to be scribed.
I don't expect this load to be more than one lecture/student. I will typically ask for a volunteer at the
beginning of the class.
Updating Wikipedia. Every student will pick a coding theory topic
that is either absent or not well documented on Wikipedia and write/edit the corresponding entry.
(An example of such a page is the one on List Decoding.) You will have the opportunity
to work on initial versions of the entry on an in-house wiki page
before the entries are posted on Wikipedia (you'll need
to get my OK before you post your entry on Wikipedia).
Homeworks. About 2 of them.
Paper presentation. Every student will give a presentation at
the end of the semester.
A list of papers has been posted on the blog.
Grading Policy
Here is a rough split of grades:
Scribing notes/Updating Wikipedia (30-40%). The scribed notes/Wikipedia
entries will be graded on
the quality of the writeup. (The scribed notes will also be graded on the
timeliness of completion.)
Homeworks (40-25%). Collaboration in groups of size at most three is
allowed (and encouraged). However, every student is expected to do their
own writeups and clearly state the names of their collaborators. More details
will be available when the homeworks are handed out.
Paper presentations (30-35%). The grade will depend on the clarity/quality
of presentation as well as the depth of material covered.
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).
