Actually, it doesn't increase much faster than linear. It's quasilinear, and so in O(n^(1+\epsilon) for all \epsilon > 0. There are a variety of such results, so most objections don't hold weight.
The paper you linked to names challenges, but it only states those in respect to reaching practical scaling, which is a result of the constant that is associated with the growth rate, but not the growth rate itself.
The paper you linked to names challenges, but it only states those in respect to reaching practical scaling, which is a result of the constant that is associated with the growth rate, but not the growth rate itself.