Wednesday, June 19
1:30-3:30 PM
Room 301

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

Registration | Hotel Information | Dormitory Information | Transportation | Speaker Index

MEM, 4/10/96