Is there a fully polynomial-time randomized approximation scheme (FPRAS) to approximate the eigenvalues (or even the largest one) of graph Laplacians?
By FPRAS, I mean the algorithm runs in time $\mbox{poly} \left( n, \frac{1}{\epsilon} \right)$ for an $\epsilon$-approximation.