These 0.99999984 solutions are not as "ugly" as it may seem. The truth is, those are not the real runtimes of the algorithms published. To make the proof simpler, they use absurd safety bounds like 2^50 that are entirely arbitrary. For example, imagine proving that 1/x^2 > 0. This proof is much harder if you include the area around x=0, as it blows up to infinity there. Instead, if you only prove it for x>=99999, it avoids this blowup and simplifies the proof, but still gets the point across. The "real" bounds of those solutions are probably much tighter, maybe even something "beautiful" like O(n*lg lg n). But the goal of the AI papers was just to show that improvement is possible, not that the bounds are perfect (which is usually much harder to prove). Over the coming weeks and months, we'll likely see a lot of tightening.