How is gas converted into stars across cosmic time? Observations of star-forming galaxies at high redshift indicate that the conditions of the interstellar medium (ISM) were remarkably distinct from typical spirals in the local universe. Nevertheless, these observations are biased towards objects brighter than L*, due to the large luminosity distances involved. Here I present a survey targeting the molecular gas in galaxies at low redshift (z ~ 0.2) with ISM conditions remarkably similar to those observed at earlier epochs, including high star formation rates and lower metallicities. CO observations performed with CARMA indicate that these galaxies follow the same star-formation law as local spirals and other galaxies at the same redshift, albeit at much higher densities. We also present recent results from our ALMA program studying galaxies down to 12 + log(O/H) ~ 8, and discuss the implications of these data to our understanding of the molecular gas reservoir and the conversion factor between CO luminosity and gas mass in environments that are simultaneously low in metal content and extremely dense.