Hardest known natural problem in P? I wonder, what is (currently) the largest number $k$, such that a natural problem is known with the following properties:


An $O(n^k)$ algorithm has been already found for the problem.
For any fixed $\epsilon&gt;0$ no $O(n^{k-\epsilon})$ algorithm is known for the same problem. (Note that a faster algorithm $may$ exist, just it is not known yet, so I am not looking for a proven lower bound.)
The problem description itself does not depend on $k$. (This condition is needed to exclude parametrized cases like "find a clique of size $k$ in an input graph, for a constant $k$.")


In a sense, such a problem might qualify as the hardest, known, natural, problem in $\bf P$ (regarding the exponent of the fastest known algorithm).
The AKS Primality testing algorithm may be a good candidate, where the best algorithm currently known version of the algorithm has $\tilde{O}(n^6)$ running time.  See Primality testing with Gaussian periods (Lenstra and Pomerance).