My research interests mainly lie in a part of mathematics known as combinatorics, and in various related areas. I spend much of my time thinking about graphs, networks and other discrete structures, both from a structural and from a probabilistic perspective. This sometimes leads me into looking at algorithms, and into connections with statistical physics.
Particular interests include partitioning and colouring problems, the reconstruction of discrete structures from various types of substructure, and the question of how uniform a combinatorial structure can be. A recent interest has been in the combinatorial structure of hard computational problems. What do typical instances of such a problem look like? Are there efficient techniques for solving a randomly chosen instance? Can an algorithm that is very bad in the worst case be very good on average?