  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 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 Song's 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}A\sqrt{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 STOC'89; Lee, Sidford FOCS'15; Cohen, Lee,
Song STOC'19] required $\Omega(n^2)$ time for this task. [...]
