Polynomial speedups with algorithms based on semidefinite programming
I'm not familiar with details of the ellipsoid method specifically for semi-definite programs, but even for linear programs, analysis of the ellipsoid method is pretty subtle.


First, one needs to bound the number of iterations of the ideal ellipsoid algorithm.  Let $E_i$ be the ellispoid used in the $i$th iteration of the ellipsoid algorithm, and let $c_i$ be its centroid.  In the ideal algorithm, a separation/membership oracle gives you a halfspace $h_i$ that contains the optimum point $x^*$ but not the centroid $c_i$.  The next ellipsoid $E_{i+1}$ is the smallest ellipsoid containing $E_i\cap h_i$.  For each $i$, we have $vol(E_{i+1}) &lt; (1-\frac{1}{n})\cdot vol(E_i)$, where $n$ is the dimension.  Thus, given a reasonable starting ellipsoid, the number of iterations is polynomial in $n$ and $\log(1/\varepsilon)$.  Computing $E_{i+1}$ from $E_i$ and $h_i$ requires (crudely) $O(n^2)$ arithmetic operations.  So the number of arithmetic operations is also polynomial in $n$ and $\log(1/\varepsilon)$.
However, some of those arithmetic operations are square roots!  It follows that the coefficients of the ideal ellipsoid $E_i$ are irrational numbers of degree $2^i$, and so there's no hope of actually computing $E_{i+1}$ exactly in any reasonable time.  So instead, one computes a close outer approximation $\tilde{E}_i \supset E_i$ at each iteration using finite precision arithmetic.  Grötschel, Lovasz, and Schrijver prove that if one uses (say) $10i$ bits of precision in the $i$th iteration, we still have $vol(\tilde E_{i+1}) &lt; O(1-\frac{1}{n})\cdot vol(\tilde E_i)$, so the number of iterations increases by at most a constant factor.  But now each arithmetic operation during the $i$th iteration (including the operations performed by the separation oracle) requires $O(i~\text{polylog}~i)$ time.


Altogether, the total running time of the ellipsoid method is very roughly the square of the number of arithmetic operations.  Since the number of arithmetic operations is polynomial in $n$ and $\log(1/\varepsilon)$, so is the running time.