How important is it to find a deterministic polynomial time algorithm to construct Ramanujan graphs?
There is already an explicit construction of Ramanujan graphs, due to Margulis and (separately) Lubotzky–Philips–Sarnak. Their construction only gives graphs with degree $p+1$ for some prime $p$. Later this was extended to cover prime powers $p$.

Recently, Marcus, Spielman and Srivastava gave a probabilistic construction of bipartite Ramanujan graphs of all degrees, and the paper appeared in FOCS 2013, and is due to appear in the Annals of Mathematics. This construction cannot even be implemented by an efficient probabilistic algorithm, and only works for bipartite graphs. In very recent work, the same authors extend their method to give bipartite Ramanujan graphs of all degrees and all sizes, in work that was submitted to FOCS 2015 (per Adam Marcus's homepage).

The community finds the recent line of work exciting not only because of the results themselves, but also because of the very interesting technique, which while (as far as I understand) not entirely new, has reached a new level of sophistication and applications. Improving on their results, either to get efficient algorithms or to remove the bipartiteness assumption, will likely require new techniques, and so will be exciting for the community.

While both papers mentioned above were submitted to FOCS, this is just due to coincidence; they might as well have been submitted to STOC. There is no real difference between these conferences, other than the time of year in which they take place, and the organization sponsoring them. SODA is considered less prestigious than FOCS and STOC.