Recently, we have made considerable progress towards a better understanding of the nature of hard computational problems. In particular, by exploiting connections between combinatorial search problems and models from statistical physics, we now have methods that enable a much finer-grained characterization of computational complexity than the standard worst-case complexity measures. These findings provide insights into new algorithmic strategies based on randomization and distributed algorithm portfolios. I will survey the recent progress in this area and I will discuss implications for the design of more robust computational systems.