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?

  • $\begingroup$ Community wiki? $\endgroup$ – Thomas Klimpel Jan 22 '18 at 0:51
  • 1
    $\begingroup$ @ThomasKlimpel, what purpose did you have in mind? See also meta.stackexchange.com/q/227290/160917. $\endgroup$ – D.W. Jan 22 '18 at 1:05
  • 2
    $\begingroup$ We discourage "list questions" (see cs.meta.stackexchange.com/q/20/755 and cs.meta.stackexchange.com/q/145/755). Note to answerers: each answer should be an complete answer to the question (with multiple examples). We don't want each answer to be a single item. If this degenerates to one item per answer, it risks being closed as "too broad", or answers risk being deleted. $\endgroup$ – D.W. Jan 22 '18 at 1:07
  • $\begingroup$ @D.W. I read both of your links carefully. Gilles wants to discourage "list questions" and Raphael wants to look more careful at the individual cases without discouraging list questions in general. The voting indicates that the cs.stackexchange community prefers Raphael's position. Your "Note to answerers:" however seems to be correct, that is the most upvoted proposal how to proceed with list questions. (I understand that you personally don't like "community wiki" answers/questions, but as a moderator you should take care not to mix your personal preferences with the community consensus.) $\endgroup$ – Thomas Klimpel Jan 22 '18 at 12:50

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/


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. Subcubic1 $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).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.