Time: Mon 2:15-4:05pm
Location: Gates 159 (Stanford)
Instructors :
and
Homepage:
http://cs369e.stanford.edu
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:
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 |
|