CS 369 E : Expanders in Computer Science

Abstract

for their meticulous note-taking. We also thank Microsoft Research and the Computer Science Department at Stanford. We had indeed advertised that we will be covering recent results in the course announcement. We had planned to cover Reingold's new result " SL=L " , which we presented in lecture as scheduled. Little did we expect that Irit Dinur would come up with a simple proof of the PCP Theorem using expanders and that we would actually present the new proof in the course, when it was hardly a few weeks old. These notes are by no means polished. Nevertheless, comments are always appreciated. 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 zigzag expanders. A large chunk of the course will be devoted to applications of expanders: