The solution space geometry of random constraint satisfaction problems Amin Coja-Oghlan Random instances of constraint satisfaction problems such as k-SAT or k-Coloring are notoriously hard for many algorithmic techniques, in particular if the density of the instance is close to the threshold for the existence of a solution. Recent non-rigorous work from the statistical physics community has led to new algorithms (e.g., "Survey Propagation") that perform emprically very well on random instances. These algorithms are based on hypotheses about the "solution space geometry" of random constraint satifaction problems, i.e., the number and relative location of the solutions. In this talk I will discuss these hypotheses as well as their algorithmic implications, and present some recent mathematically rigorous work on proving some of the hypotheses. Parts of the talk are based on joint work with Dimitris Achlioptas and Alan Frieze.