Abstract

The systematic study of random graphs commenced with the seminal work of Erd" os and Renyi in the 1960s. Beyond the classical connections and synergies between random graphs and computer science, over the last few years a new exciting connection between random graphs and statistical inference has been discovered. These connections have led to important new insights on computational problems and statistical inference problems and to new methods for the analysis of random graphs or random discrete structures in general. In addition, since the late 1990s an insightful approach called the cavity method by physicists has been applied to put forward predictions on structural properties of random graphs and their phase transitions. More recently, it has inspired new algorithms for statistical inference problems such as message passing algorithms and novel spectral algorithms. With this workshop we hope to stimulate research and foster new exciting interdisciplinary collaborations between researchers with different backgrounds and expertise in random graphs, computer science, probability, statistics, statistical inference and information theory.