[seagaia]

+1 For someone helping us understand this - is there now an implementation (or could someone now given this paper, produce an implementation) that will run in this new time? Or is it just (as FaceKicker asked) a new analysis?

[xyzzyz]

Most likely, it's not a practical algorithm, in the sense that it would yield practical time improvement only for unfeasibly large matrices. It does not matter for theorists, though -- for them it's still important result.