Before revision:  The same paper also showed that O(n ^ 3) is the best possible running time for any algorithm using the so-called decomposition strategy , which underlies almost all the known algorithms for this problem.
After revision:  The same paper also showed that O(n ^ 3) is the best possible running time for any algorithm using the so-called decomposition strategy , which underlies almost all the known algorithms for this problem.