Abbas Mehrabian

Postdoctoral Research Fellow

Linear Algebra and its applications in Algorithm Design (I, II)

  Computer Engineering Department, Floor 4, Kharazmi Hall
  Thursday, 31 December 2015
  15:00 - 16:00

Abstract

In recent years we have seen several breakthroughs in computer science, in particular in graph algorithms, that are based on linear algebraic insights and methods. I will present two highlights with the aim of convincing the audience to take linear algebra more seriously.

Linear algebraic tools have been successfully applied to the algorithmic problem of finding a maximum matching in a graph, resulting in the fastest known algorithm for dense graphs. This line of research was started by Rabin and Vazirani (J of Algorithms’89), followed by Micha and Sankowski (FOCS’04) and Harvey (winner of the best student paper award of FOCS’06), who showed a maximum matching in an n-vertex graph can be found essentially in the time needed to multiply two nxn matrices. In the first talk (Wednesday) I will describe Rabin-Vazirani’s algorithm and Micha-Sankowski’s O(n^3) speed up, and an overview of Harvey’s algorithm. A familiarity of the audience with basic notions of linear algebra, such as the determinant and inverse of a matrix, is assumed.

Another fundamental problem for which linear algebraic approaches turned out to be quite successful is the maximum flow problem. Christiano, Kelner, Madry, and Spielman (winner of the best paper award of STOC’11) showed how to find an approximation of the maximum flow in an m-edge undirected graph in time O(m^4/3). After a sequence of improvements, Peng (arXiv, November 2015) showed how to perform this task in time O(m polylog(m)). In the second talk (Thursday) I will give a high-level outline of the Christiano et al.’s algorithm, which uses insights from the theory of electrical networks, fast Laplacian solvers, and the multiplicative weight update method. The talk is stand-alone and will be accessible to all audience.

Bio

Abbas Mehrabian received his BSc degrees in 1388 in Computer Engineering and Mathematics from Sharif University. He then moved to Waterloo and completed a PhD in Combinatorics and Optimization in 1394. He is now a postdoctoral researcher at the University of British Columbia. His research interests are Graph Theory, Probability Theory and their applications in Computer Science.