Interior point algorithms for solving linear programs have been studied extensively for a long time [e.g. Karmarkar 1984; Lee, Sidford FOCS14; Cohen, Lee, Song STOC19]. 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 [STOC19]. 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 Vaidyas 30 years old $O(n^{2.5} log(n/delta))$ bound [FOCS89]. In this paper we show that one can also settle the deterministic setting by derandomizing Cohen et al.s $tilde{O}(n^omega log(n/delta))$ time algorithm. This allows for a strict $tilde{O}(n^omega log(n/delta))$ time bound, instead of an expected one, and a simplified analysis, reducing the length of their proof of their central path method by roughly half. Derandomizing this algorithm was also an open question asked in Songs PhD Thesis. The main tool to achieve our result is a new data-structure that can maintain the solution to a linear system in subquadratic time. More accurately we are able to maintain $sqrt{U}A^top(AUA^top)^{-1}Asqrt{U}:v$ in subquadratic time under $ell_2$ multiplicative changes to the diagonal matrix $U$ and the vector $v$. This type of change is common for interior point algorithms. Previous algorithms [e.g. Vaidya STOC89; Lee, Sidford FOCS15; Cohen, Lee, Song STOC19] required $Omega(n^2)$ time for this task. [...]
Download