One method is to reduce the computation to that of computing matrix multiplication of $n \times n$ matrices. In particular, the determinant of a symbolic matrix can be computed in $O(n^{\omega})$ arithmetic operations, where $\omega < 2.376$ is the matrix multiplication exponent, and from a symbolic determinant of course one can recover all eigenvalues. However, since the operations here will be over polynomials of degree $n$ with coefficients in $m$ bits, this method would take about $O(n^{1+\omega} m)$ time to get $m$ bits of the eigenvalues.

More complex methods can get you the eigenvalues in $O(n^3 + n^2 \log^2 n \log b)$ time, where the eigenvalues are approximated to within $2^{-b}$. For some structured matrices you can get about $O(n^{\omega})$. See

>	Victor Y. Pan, Zhao Q. Chen: The Complexity of the Matrix Eigenproblem. STOC 1999: 507-516

(Actually it appears this paper never appeared in a journal form, so study it very carefully if you are serious about this problem.)

I don't see a simple way to exploit the fact that (a) it is symmetric and (b) you just want to find the smallest nonzero eigenvalue. It seems doubtful to me that you could do this much faster than $O(n^{\omega})$ (without finding *all* nonzero eigenvalues faster than this), but this is just based on intuition, not fact.