So, the pseudo-FFT exploits algorithmic similarity between DFT and multiplication to translate part of the DFT work into multiplication work, which is O(1) in the exact arithmetic model.
Thus, the magnitudes of the numbers being multiplied grow superpolynomially with n (the DFT problem size): because the robot's stuffing its work in there and using it as an oracle.
Did I get that much right? What a cool hack.