What are the examples of problems which first had large polynomial time complexity algorithms but later the complexity was reduced significantly?

Question

Arora-Barak says

It has also happened a few times that the first polynomial-time algorithm for a problem had high complexity, say $n^{20}$, but soon somebody simplified it to say an $n^5$ time algorithm

What are some examples of the above statement? I know AKS is one, are there any other?

Answer 1

Approximating volume of convex bodies

In Dyer et al.: A random polynomial-time algorithm for approximating the volume of convex bodies. Journal of the ACM (JACM) 38.1 (1991): 1-17. a $O(n^{19})$ approximation algorithm was proposed.

The work of Lovász et al.: Simulated annealing in convex bodies and an $O^*(n^4)$ volume algorithm. Journal of Computer and System Sciences 72.2 (2006): 392-417. proposed an $O^*(n^4)$ algorithm, where the asterisk denotes that the dependence on error parameters and on logarithmic factors in $n$ is not shown (according to their paper).

---

Maybe you may find this thread useful: https://cstheory.stackexchange.com/questions/6660/polynomial-time-algorithms-with-huge-exponent-constant/

Answer 2

Khachiyan's ellipsoid method (1979) for linear programming famously proved the polynomial-time solvability of linear programs, even so the older simplex algorithm is much faster than the ellipsoid method in practice. But it inspired new lines of research in linear programming, and Karmarkar's algorithm (1984) was able to reduce the exponent and compete again the simplex algorithm in practice:

Denoting $n$ as the number of variables and $L$ as the number of bits of input to the algorithm, Karmarkar's algorithm requires $O(n^{3.5} L)$ operations on $O(L)$ digit numbers, as compared to $O(n^6 L)$ such operations for the ellipsoid algorithm. The runtime of Karmarkar's algorithm is thus $$O(n^{3.5} L^2 \cdot \log L \cdot \log \log L)$$ using FFT-based multiplication.

However, even so I vaguely remember the same $O(n^6)$ bound for the ellipsoid method from a lecture, I doubt that it is a sharp bound. Wikipedia says in a different article that

this algorithm uses $O(n^4L)$ pseudo-arithmetic operations on numbers with $O(L)$ digits.

---

The Ford–Fulkerson method (1956) for computing the the maximum flow in a flow network is not fully specified, but a reasonable implementation (1972) achieved a running time of $O(V E^2)$. Dinic's algorithm (1970) includes additional techniques that reduce the running time to $O(V^2 E)$. The Goldberg-Tarjan push-relabel methods (1988) use completely different paradigms and achieve significantly smaller (theoretical and practical) runtimes:

The variant based on the highest label node selection rule has $O(V^2\sqrt{E})$ time complexity and is generally regarded as the benchmark for maximum flow algorithms. Subcubic¹ $O(VE\log(V^2/E))$ time complexity can be achieved using dynamic trees, although in practice it is less efficient.

To summarize, an initial $O(n^5)$ got reduced to $O(n^4)$ by including additional techniques in less than 15 years, and more than 15 additional years later, different paradigms achieved $O(n^3)$.

---

1. _{Whether $O(VE\log(V^2/E))$ is subcubic is debatable. $E=o(V^2)$ is quite common in practice, but $O(V^2\sqrt{E})$ will also be subcubic in that case, and the corresponding algorithm apparently works better in practice. But one would have to fix Wikipedia first (same for the $O(n^4L)$ vs $O(n^6L)$ runtime for ellipsoid method issue).}