  In this paper we provide an $\tilde{O}(nd+d^{3})$ time randomized algorithm
for solving linear programs with $d$ variables and $n$ constraints with high
probability. To obtain this result we provide a robust, primal-dual
$\tilde{O}(\sqrt{d})$-iteration interior point method inspired by the methods
of Lee and Sidford (2014, 2019) and show how to efficiently implement this
method using new data-structures based on heavy-hitters, the
Johnson-Lindenstrauss lemma, and inverse maintenance. Interestingly, we obtain
this running time without using fast matrix multiplication and consequently,
barring a major advance in linear system solving, our running time is near
optimal for solving dense linear programs among algorithms that do not use fast
matrix multiplication.
