Wednesday, June 19
1:30-3:30 PM
Room 301
MS10
Eigenvalues and Expanders
Eigenvalues play a key role in controling the isoperimetries and discrepancies of a graph. Consequently, expander graphs with good eigenvalue bounds have a wide range of applications in communication networks, randomized and derandomized algorithms, parallel computing and distributed computation, to name a few. The speakers will present recent developments on eigenvalues of subgraphs with boundary conditions with applications to enumeration and approximation algorithms, on disjoint path problems in expander graphs and algorithms for finding paths for rapidly mixing random walks, and on constructing error-correcting codes using expander graphs and the practical and theoretical significance of these codes.
Organizer: Fan R.K. Chung
University of Pennsylvania
- 1:30 Disjoint Paths in Expander Graphs
- Alan Frieze, Carnegie Mellon University
- 2:00 Linear-Time Encodable and Decodable Error-Correcting Codes
- Daniel A. Spielman, Massachusetts Institute of Technology
- 2:30 Eigenvalues of Subgraphs with Boundary Conditions
- Fan R.K. Chung, Organizer
MEM, 4/10/96