Grant: Discovery Grants Program - Individual
University of Waterloo
$48,000.00
New Methods for the Analysis of Randomized Algorithms
FY 2024-25
Summary
Randomness is a remarkably powerful resource in the design of efficient algorithms. The analysis of randomized algorithms required to obtain provable guarantees regarding their correctness and efficiency introduces significant challenges, and many basic questions about the general power of randomness in efficient computation remain open problems in complexity theory.
The proposed research aims to overcome these important challenges by developing and exploiting new algorithmic, mathematical, and information-theoretic methods for the design and analysis of randomized algorithms. These methods will lead to new efficient algorithms for multiple fundamental computational tasks, to new methods for determining the limitations of randomized algorithms, and to new insights on the interplay between randomness and computation.
This research will provide an important step in reaching the high-level long-term goal of establishing a complete, unified, and sound theoretical foundation for randomized algorithms.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
RGPIN-2022-03329
Name nom
Blais, Eric
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2024
Competition year année de concours
2022
Award amount
48000
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
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
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
New Methods for the Analysis of Randomized Algorithms
Keywords
randomized algorithms; sublinear-time algorithms; forecasting algorithms; query complexity; computational complexity; communication complexity; property testing; boolean functions; minimax theorems; high-dimensional geometry
Application summary
Randomness is a remarkably powerful resource in the design of efficient algorithms. The analysis of randomized algorithms required to obtain provable guarantees regarding their correctness and efficiency introduces significant challenges, and many basic questions about the general power of randomness in efficient computation remain open problems in complexity theory.
The proposed research aims to overcome these important challenges by developing and exploiting new algorithmic, mathematical, and information-theoretic methods for the design and analysis of randomized algorithms. These methods will lead to new efficient algorithms for multiple fundamental computational tasks, to new methods for determining the limitations of randomized algorithms, and to new insights on the interplay between randomness and computation.
This research will provide an important step in reaching the high-level long-term goal of establishing a complete, unified, and sound theoretical foundation for randomized algorithms.