Abstract: Focusing on some fundamental constraint satisfaction problems defined on sparse random graphs (e.g. random k-sat, random q-coloring) I will start summarizing the rich phase diagram of the solution space which has been derived using powerful techniques from statistical mechanics of disordered systems. I will then discuss the implications of some of these phase transitions for the behaviour of smart algorithms searching for solutions. In the second part, I will consider the problem of inferring a signal from noisy and/or incomplete data within the Bayesian framework called the teacher-student scenario. I will discuss the corresponding phase diagrams and how phase transitions may affect the performances of inference algorithms based on message-passing and Monte Carlo sampling.