Improved Algorithms for Dynamic Matrix Inverse

Speaker(s)

Jan van der Brand

Affiliation

KTH

Date

July 19, 2018, 12:15 p.m.

Room

room 5870

Seminar

Seminar Algorithms

---

The dynamic matrix inverse problem is to maintain the inverse of a matrix undergoing element and column updates. It is the main subroutine behind the best algorithms for many dynamic problems, such as maintaining the largest eigenvalue, rank and determinant of a matrix and maintaining reachability, distances, maximum matching size, and k-paths/cycles in a graph. Prior best bounds for most of these problems date back to more than a decade ago [Sankowski FOCS’04, COCOON’05, SODA’07; Kavitha FSTTCS’08; Mucha and Sankowski Algorithmica’10; Bosek et al. FOCS’14].

---