The reported running time in the stochastic setting is highly conservative: we did not parallelize the sampling (i.e., constructing \(A\Omega \)  in line 4 of Algorithm ). Furthermore, as noted earlier (and further described in the appendix), standard Gaussian matrices are theoretically "nice" to work with but structured random matrices, such as SRFT matrices which compute \(Y=A\Omega \)  via a subsampled FFT [1]} will offer superior running times.
