What is the meaning of 'moderately exponential' running time?
Moderately exponential is not a widely accepted term in general theoretical computer science, though it might have a widely accepted meaning in the area to which the paper you are citing belongs.

From context, it seems that the meaning here is $\exp O(n^\alpha)$ for $\alpha &lt; 1$; an exponential running time would be $\exp O(n)$ or worse.