Improved Algorithms for Dynamic Matrix Inverse

Prelegent(ci)

Jan van der Brand

Afiliacja

KTH

Termin

19 lipca 2018 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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].

---