Random Structures and Algorithms

The study of random combinatorial structures was initiated some 50 years ago by a series of papers by Paul Erdos and Alfred Renyi. It has since grown substantially and we will survey some of the results in the area. Many of the existence questions come along with natural computational problems. These problems are usually computationally hard i.e NP-hard, but one can show that there are algorithms whose  performance on these problems is much better than worst-case would suggest. We will also discuss this area of "average case analysis".