BARC talk by Jan van den Brand #2

Tuesday, 10 March 2020, Jan van den Brand, third year PhD student at KTH in Stockholm, will give another talk at BARC. This time on "A Deterministic Linear Program Solver in Current Matrix Multiplication Time".

Title:
A Deterministic Linear Program Solver in Current Matrix Multiplication Time

Abstract:
Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS'14; Cohen, Lee, Song STOC'19]. For linear programs of the form $\min_{Ax=b, x \ge 0} c^\top x$ with $n$ variables and $d$ constraints, the generic case $d = \Omega(n)$ has recently been settled by Cohen, Lee and Song [STOC'19]. Their algorithm can solve linear programs in $\tilde O(n^\omega \log(n/\delta))$ expected time, where $\delta$ is the relative accuracy. This is essentially optimal as all known linear system solvers require up to $O(n^{\omega})$ time for solving $Ax = b$. However, for the case of deterministic solvers, the best upper bound is Vaidya's 30 years old $O(n^{2.5} \log(n/\delta))$ bound [FOCS'89]. In this talk I will show that one can also settle the deterministic setting by derandomizing Cohen et al.'s algorithm via techniques from the area of dynamic algorithms. By using data structures for the so called dynamic matrix inverse problem, we obtain a deterministic $\tilde{O}(n^\omega \log(n/\delta))$ time bound, instead of an expected one.

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.