Discrete mathematics, computer science and statistical physics have a shared heritage, dating back at least to the birth of modern computing. In recent years, an interdisciplinary area has blossomed at the junction of these fields. Insights from the mathematical and physical sciences have brought significant contributions to solving basic computational challenges. Researchers have successfully applied techniques from the study of phase transitions to analyze NP-complete problems such as satisfiability and graph coloring. This is leading to a new understanding of the structure of these problems, new ways to analyze algorithmic performance, and most excitingly, effective new algorithms. At the same time, computer science has provided significant new perspectives in probability and combinatorics. The study of complex networks has reinvigorated the graph theory community, providing a rich source of new models that aim at capturing the essential structure of real-world data.

This work has been funded by the DOE Laboratory-Directed Research and Development (LDRD) projects DR 2006117 and ER 20030137 at Los Alamos National Laboratory, the NSF award CCF-0829945, and the Air Force Office of Scientific Research MURI award FA9550-10-1-0569.