Before revision:  Furthermore, we show how to compute the k-dimensional persistent homology of these n points in running time O(n^2(k+\log n)), which is nearly quadratic in the number of vertices n . This improves upon the traditional persistent homology algorithm, which is cubic in the number of simplices of dimension at most k+1, and hence of running time O(n^{3(k+2)})
After revision:  Furthermore, we show how to compute the k-dimensional persistent homology of a filtration of clique complexes of cyclic graphs on n vertices. This is nearly quadratic in the number of vertices n . This improves upon the traditional persistent homology algorithm, which is cubic in the number of simplices of dimension at most k+1, and hence of running time O(n^{3(k+2)})