The number of explicit constructions of expander graphs is still limited.  I haven't kept up with the latest developments but I think this one is still open:

>Find a 16-regular multigraph on $n$ vertices whose second largest eigenvalue $\lambda_2<8$.

Existence follows from a deep probabilistic result of Joel Friedman.  It's possible that one can turn Friedman's proof into a <i>randomized</i> polynomial time algorithm because one can certainly test whether $\lambda_2<8$ in polynomial time, but I don't think there is a <i>deterministic</i> polynomial time algorithm known.