Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

University of Waterloo

$34,000.00

Theoretical foundation of sublinear-time algorithms

FY 2017-18

Summary
Many areas of science are currently undergoing a dramatic transformation: with rapid advances in data collection technologies, molecular biologists can now measure the level of expression of every gene in a cell; physicists can now record the details of collisions of subatomic particles; astronomers can now obtain detailed pictures of the farthest reaches of the universe; etc. The rich datasets that can now be collected offer many exciting scientific opportunities, but they also introduce significant new computational challenges. Sublinear-time algorithms are one of the powerful tools that will help us meet these challenges. A sublinear-time algorithm is an algorithm that produces its output after inspecting only a tiny fraction of its input and executing a number of computational steps that is asymptotically smaller than the size of the input. The research described in this proposal aims to provide a solid theoretical foundation for the development and the analysis of these algorithms. This will be done by developing new algorithmic techniques for designing sublinear-time algorithms, new mathematical tools to analyze these algorithms and establish their limitations, and new connections to other areas of theoretical computer science.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2015-03907
Name nom
Blais, Eric
Department département
Computer Science, David R. Cheriton School of - Computer Science, David R. Cheri
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2015
Award amount
34000
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
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
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
Theoretical foundation of sublinear-time algorithms
Keyword
NSERC
Application summary
Many areas of science are currently undergoing a dramatic transformation: with rapid advances in data collection technologies, molecular biologists can now measure the level of expression of every gene in a cell; physicists can now record the details of collisions of subatomic particles; astronomers can now obtain detailed pictures of the farthest reaches of the universe; etc. The rich datasets that can now be collected offer many exciting scientific opportunities, but they also introduce significant new computational challenges. Sublinear-time algorithms are one of the powerful tools that will help us meet these challenges. A sublinear-time algorithm is an algorithm that produces its output after inspecting only a tiny fraction of its input and executing a number of computational steps that is asymptotically smaller than the size of the input. The research described in this proposal aims to provide a solid theoretical foundation for the development and the analysis of these algorithms. This will be done by developing new algorithmic techniques for designing sublinear-time algorithms, new mathematical tools to analyze these algorithms and establish their limitations, and new connections to other areas of theoretical computer science.