Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Toronto

$62,000.00

Probabilistic Graph Theory and Random Constraint Satisfaction Problems

FY 2016-17

Summary
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.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2014-03858
Name nom
Molloy, Michael
Department département
Computer and Mathematical Sciences (Scarborough) - Computer and Mathematical Sci
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2014
Award amount
62000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2712
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Theory of computation
Research subject fr
Théorie de calcul
Partie
3
Nb partie
5
Application title
Probabilistic Graph Theory and Random Constraint Satisfaction Problems
Keyword
NSERC
Application summary
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.