Course Announcement: CS369E, Expander in Computer Science - Spring 2005

Expanders, constructions and their applications

Time: Mon 2:15-4:05pm
Location: Gates 159 (Stanford)
Instructors : and

Expanders in Computer Science

Over the past few decades, expanders have played a pervasive role in diverse fields of computer science - network design, derandomization, distributed computing, random walks, error-correcting codes, metric embeddings etc. Informally, an expander is a sparse graph which is nevertheless highly connected. In this course, we will study these expander graphs and several of their applications.

As part of this course, we will study the relationship between expansion and eigen values. We will then look at various constructions of expanders - Margulis, LPS and zig-zag expanders. A large chunk of the course will be devoted to applications of expanders:

  1. Random walks and universal sequences
  2. Derandomization
    (including Reingold's "SL=L" result)
  3. Error Correcting Codes
  4. Distributed Computing
  5. Isoperimetric problems

The course will reach the cutting-edge of current research in this area, covering some results from within the last year. At the same time, the concepts we will cover are general and useful enough that hopefully anyone with an interest in the theory of computation or combinatorics could find the material appealing.

Instructors : and

Prahladh Harsha
Valid HTML 4.01! Valid CSS! Get Firefox!