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