CSAIL Event Calendar: Previous Series

Graph Connectivity, Network Coding, Expander Graph, and Matrix Rank.

Speaker: Lap Chi Lau , The Chinese University of Hong Kong
Date: October 27 2011
Time: 4:15PM to 5:15PM
Location: 32-G449 Patil/Kiva
Host: Dana Moshkovitz and Costis Daskalakis, CSAIL, MIT

We present a new algebraic formulation to compute edge connectivities in a directed graph, using the ideas developed in network coding. This reduces the problem of computing edge connectivities to solving systems of linear equations, thus allowing us to use tools in linear algebra to design new algorithms. Using the algebraic formulation we obtain faster algorithms for computing single source edge connectivities and all pairs edge connectivities, in some settings the amortized time to compute the edge connectivity for one pair is sublinear. Through this connection, we have also found an interesting use of expanders and superconcentrators to design fast algorithms for some graph connectivity problems.

Finally we show a recent development on using the above ideas to design fast algorithms for computing matrix rank.

Joint work with Ho Yee Cheung, Tsz Chiu Kwok, Kai Man Leung.

See other events that are part of Theory Colloquium 2011/2012

See other events happening in October 2011