Grant: Discovery Grants Program - Individual
McGill University
$85,000.00
Applications of probability theory in the design and analysis of algorithms
FY 2011-12
Summary
We seek to further the understanding of probabilistic phenomena that occur in the design and behavior of algorithms and data structures. The long-term plan has four axes of research:
(1) The in-depth analysis of random trees and random structures that are practically relevant. We will in particular focus on families of randomized trees that act on arbitrary non-random high-dimensional data, on random tries (in the context of the bit model of complexity), and on general web models called scaled attachment recursive dags.
(2) Random networks with geometric, connectivity, directional, or time-lapse restrictions. Connectivity thresholds and emergence of giant components are of particular interest.
(3) The continued effort to design universally consistent but also computationally efficient classifiers, with particular attention given to tree classifiers.
(4) The development of new paradigms for random variate generation and the exact simulation of objects or processes that hitherto could either not be generated in an exact manner, or could at best be generated inefficiently.
Program
Discovery Grants Program - Individual
Recipient
Location
Quebec, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
3456-2011
Name nom
Devroye, Luc
Department département
Computer Science, School of
Organization id
61
Institution établissement
McGill University
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2011
Competition year année de concours
2011
Award amount
85000
Program id
RGPIN
Program nane 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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
5
Application title
Applications of probability theory in the design and analysis of algorithms
Keyword
NSERC
Application summary
We seek to further the understanding of probabilistic phenomena that occur in the design and behavior of algorithms and data structures. The long-term plan has four axes of research:
(1) The in-depth analysis of random trees and random structures that are practically relevant. We will in particular focus on families of randomized trees that act on arbitrary non-random high-dimensional data, on random tries (in the context of the bit model of complexity), and on general web models called scaled attachment recursive dags.
(2) Random networks with geometric, connectivity, directional, or time-lapse restrictions. Connectivity thresholds and emergence of giant components are of particular interest.
(3) The continued effort to design universally consistent but also computationally efficient classifiers, with particular attention given to tree classifiers.
(4) The development of new paradigms for random variate generation and the exact simulation of objects or processes that hitherto could either not be generated in an exact manner, or could at best be generated inefficiently.