BARC talk by Jan van den Brand #1

Tuesday, 3 March 2020, Jan van den Brand, third year PhD student at KTH in Stockholm, will give a talk on "Dynamic algorithms for algebraic and graph problems".

Title:
Dynamic algorithms for algebraic and graph problems

Abstract:
Efficient data-structures play an important role in designing fast algorithms. In this talk I will present data-structures that efficiently maintain the solution to algebraic problems such as linear systems, rank, inverse etc. and graph problems such as matchings, reachability, and distances. These data-structures lead to improvements for iterative algorithms, such as linear program solvers. We will also see how algebraic techniques and ideas from the symbolic computation community can be used to answer open questions in the area of graph data-structures, such as maintaining single-source distances in a changing graph in sub-quadratic time, and handling large batch updates in failure sensitive distance oracles.

Bio:
Jan is a third year PhD student at KTH in Stockholm, Sweden, and he works together with the dynamic and distributed algorithms group of Danupon Nanongkai. Before that, Jan did his Bachelors and Masters at the Goethe University in Frankfurt, Germany.
His research explores improvements and limits of algebraic techniques for data-structures (dynamic algorithms) and their application in convex optimization.