Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Toronto

$50,000.00

Probabilistic graph theory and theoretical computer science

EF 2012-13

Résumé
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. More recently, random structures have been recognized as a vast source for difficult inputs that can be used for the testing and refinement of algorithms. 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 the areas which involve probability.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
184038-2009
Name nom
Molloy, Michael
Department département
Computer and Mathematical Sciences (Scarborough)
Organization id
31
Institution établissement
University of Toronto
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2009
Award amount
50000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
Research subject code
2914
Research subject group en
Pure mathematics
Research subject group fr
Mathématiques pures
Research subject en
Combinatorics
Research subject fr
Combinatoire
Partie
4
Nb partie
5
Application title
Probabilistic graph theory and theoretical computer science
Keyword
NSERC
Application summary
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. More recently, random structures have been recognized as a vast source for difficult inputs that can be used for the testing and refinement of algorithms. 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 the areas which involve probability.