Title: Expander graphs - a survey (I)
Speaker: Eyal Rozenman California Institute of Technology
Time: 2008-04-25 11:00-2008-04-25 12:00
Venue: FIT Building 4-603, Tsinghua University

Abstract:

Expander graphs are ubiquitous in theoretical computer science and mathematics, with uses ranging from derandomization to construction of manifolds. We will survey several constructions of expanders (old and new) and perhaps (depending on time and audience demand) we'll see some applications of expanders as well. Along the way we will encounter group representations, Cayley graphs, isoperimetric inequalities and more.
 



Short Bio:

Eyal Rozenman is a Professor in California Institute of Technology. His research interests are various models of random graphs and their properties; expander graphs, extractors, explicit constructions, and the interplay between algebra and combinatorics in this area; extremal problems in combinatorics.