Applied Extremal Combinatorics

18.409 Topics in Theoretical Computer Science

Instructor: Dan Spielman.

This class meets TTh 2:30-4:00 in room 8-119.

Watch this page as the room may change.


Course Announcement

This course covers topics in extremal combinatorics that are useful for theoretical computer science and coding theory. This year, we will focus on extremal graph theory and its interaction with coding theory.

This course is designed for graduate students with experience in combinatorics, theoretical computer science, or coding theory. Some knowledge of group theory and linear algebra is necessary.

For each lecture, some student will produce a nice set of lecture notes (for example, see the notes from the last time I taught this class or from Advanced Complexity Theory). This task will be divided evenly among the students taking the class for credit.

The following is a list of the topics that I presently plan to discuss. We can adjust this list to satisfy the interests of those in the class.