Grant: Discovery Grants Program - Individual
McGill University
$55,000.00
Applications of probability theory in the design and analysis of algorithms
EF 2024-25
Résumé
The proposed research focuses on the analysis of algorithms, computational methods and data structures that are efficient "on the average."
We broaden our investigation of random binary search trees, quadtrees, m-ary search trees, tries, digital search trees, suffix trees and efficient multidimensional search trees such as the squarish k-d tree. We focus in particular on tree parameters such as the height, since those are of primordial importance in computations. The notion of "split trees", which we introduced in 1998, will be generalized to capture more models of random trees. Random space partition trees occurring in pattern recognition, computational geometry, and nearest neighbour search will receive special attention. In classification, other parameters appear crucial, such as the diameters of the sets in the partition. The theoretical relationship of these parameters with the size of the data set and the dimension of the space will be studied.
New problems in the analysis of random graphs and random networks include the detection of the first node, sometimes called "patient zero". One of the goals is to return a hopefully small set of nodes that contain the first node with high probability. Our proposal deals with the algorithms for this problem, and with the theoretical analysis that proves the optimality, via both upper and lower bounds, of the proposed methods. We will also look at the related problem of root bit estimation, when the root of the tree or network gets broadcast or propagated along edges but mutates with small probability p during each transmission. The user observes the values at nodes far away from the root, for example, in generation n, ad is then asked if the root's bit can be estimated or reconstructed. In some cases, one can't do better than random guessing, while in other cases, one can indeed beat random guessing. We want to identify this phase transition for many types of trees and networks.
This proposal also deals with challenging problems in random number generation. For example, how does one generate the n eigenvalues of an nxn random matrix efficiently? Since these can't be computed exactly for n>5, one has to use indirect ways to proceed. For gaussian matrices for example, we would like to develop a polynomial expected time algorithm, but even that seems a serious challenge. On a related topic, we will continue to develop the foundations of approximate random number generation when only random bits are available, building on the work of Knuth and Yao.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2024-04164
Name nom
Devroye, Luc
Department département
Computer Science
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
2024
Competition year année de concours
2024
Award amount
55000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
Field of research list names en
Not available
Field of research list names fr
Non disponible
Socioeconomic objective list names en
Not available
Socioeconomic objective list names fr
Non disponible
Application title
Applications of probability theory in the design and analysis of algorithms
Keywords
analysis of algorithms; algorithm design; data structures; random number generation; random graphs; expected time complexity; pattern recognition; machine learning; pattern recognition; probabilistic methods
Application summary
The proposed research focuses on the analysis of algorithms, computational methods and data structures that are efficient "on the average."
We broaden our investigation of random binary search trees, quadtrees, m-ary search trees, tries, digital search trees, suffix trees and efficient multidimensional search trees such as the squarish k-d tree. We focus in particular on tree parameters such as the height, since those are of primordial importance in computations. The notion of "split trees", which we introduced in 1998, will be generalized to capture more models of random trees. Random space partition trees occurring in pattern recognition, computational geometry, and nearest neighbour search will receive special attention. In classification, other parameters appear crucial, such as the diameters of the sets in the partition. The theoretical relationship of these parameters with the size of the data set and the dimension of the space will be studied.
New problems in the analysis of random graphs and random networks include the detection of the first node, sometimes called "patient zero". One of the goals is to return a hopefully small set of nodes that contain the first node with high probability. Our proposal deals with the algorithms for this problem, and with the theoretical analysis that proves the optimality, via both upper and lower bounds, of the proposed methods. We will also look at the related problem of root bit estimation, when the root of the tree or network gets broadcast or propagated along edges but mutates with small probability p during each transmission. The user observes the values at nodes far away from the root, for example, in generation n, ad is then asked if the root's bit can be estimated or reconstructed. In some cases, one can't do better than random guessing, while in other cases, one can indeed beat random guessing. We want to identify this phase transition for many types of trees and networks.
This proposal also deals with challenging problems in random number generation. For example, how does one generate the n eigenvalues of an nxn random matrix efficiently? Since these can't be computed exactly for n>5, one has to use indirect ways to proceed. For gaussian matrices for example, we would like to develop a polynomial expected time algorithm, but even that seems a serious challenge. On a related topic, we will continue to develop the foundations of approximate random number generation when only random bits are available, building on the work of Knuth and Yao.