Probabilistic Graph Theory and Random Constraint Satisfaction Problems

点击翻译按钮获取中文摘要

My research program encompasses many aspects of graph theory and related fields, and their role in theoretical computer science. Much of my work in these areas involves probability.******Graph theory is a fascinating and important pure mathematical field which, with the advent of modern computing, gained a new importance because of its applications. Many of the problems that arise in computer science are best modelled with graphs. For example, massive networks are massive graphs and the problem of finding good schedules is a graph colouring problem. So the use of graph theory to study computing has grown immensely.******One of the most important modern trends in graph theory is the use of tools and concepts from probability. The probabilistic method is a powerful and elegant tool for proving theorems and for designing algorithms. The use of random choices has led to the development of much simpler and more efficient algorithms for many fundamental problems. When studying the behaviour of an algorithm, we often ask how it performs on an average input, which amounts to analyzing its behaviour on a random input. This has led to a whole new need for the study of random graphs, a mathematical field that was introduced by Erdos and Renyi in the 1950's. Random structures have been recognized as a vast source for difficult inputs that can be used for the testing and refinement of algorithms.******Many of the most important problems in the field of random structures, eg colouring random graphs and the satisifiability of random boolean formulae, fall under the category of random constraint satisfaction problems. This area has attracted intense interest from disciplines including computer science, mathematics and physics. Recently, most of the leading work in this area has revolved around a collection of hypotheses developed by statistical physicists. For the most part, these hypotheses are not rigorously established, but they are developed using very heavy mathematical analysis. They explain many known phenomena and predict others involving, eg the values of some intensively sought parameters (the 'satisfiability thresholds') ad the longstanding observation that such problems tend to be algorithmically very challenging. Much of my research involves grounding these hypotheses with rigorous proofs and understanding their implications.**