Linear Programming asks for $x\in\mathbb R^n$ such that $Ax\leq L$ holds where $A\in\mathbb R^{m\times n}$ and $L\in\mathbb R^m$ are given. Karmarkar has shown that $\ell$ is the number of bits of input to the algorithm then we can find $x$ in$O(n^{3.5} \ell)$ operations on $O(\ell)$ digit numbers, as compared to $O(n^6 \ell)$ such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus $(n^{3.5} \ell^2 \log \ell \log \log \ell)$ using fast integer multiplication.
What is the best algorithm and its complexity that is currently known and what is believed to be the optimal?
What is the best when $n$ or $m$ is fixed?
