Large 00004

Matrix Rank and Combinatorial Optimization

Lap Chi Lau

Recorded 14 June 2012 in Lausanne, Vaud, Switzerland

Event: SuRI - I&C - Summer Research Institute


First we survey some previous work on designing fast linear algebraic algorithms for combinatorial optimization problems. Then we present a new algebraic formulation for computing edge connectivities, using the ideas developed in network coding. Then we present a fast "combinatorial" algorithm for computing matrix rank using expander graphs, and discuss its applications. Finally we conclude with some open problems in this area.

Watched 2376 times.