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 concentrates on areas which involve probability.**Graph theory is a fascinating and important pure mathematical field which, with the advent of the computer age, gained a new importance because of its applied aspects. Many of the problems that arise in computer science are best modelled by graphs. For example, massive networks are massive graphs and the problem of finding good schedules is what is known as a graph colouring problem. Thus, over the past few decades, 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 theory. The probabilistic method is a powerful and elegant tool for proving theorems. Also, the use of random choices in algorithms has led to the development of much simpler and more efficient methods for many important 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, long before its importance to computer science was realized. *In more recent decades, 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 this field, eg. colouring of random graphs and random instances of boolean formulae, fall under the category of random constraint satisfaction problems. This area has attracted intense interest from disciplines including mathematics, computer science and physics. Recently, much of the leading research in this area has revolved around a collection of hypotheses developed by physicists. For the most part, these hypotheses are not rigorously established, but they are developed using substantial mathematical analysis. They explain many known phenomena and predict others involving, eg. the values of some intensively sought parameters (the "satisfiability thresholds''), and the long-standing 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.