Grant: Discovery Grants Program - Individual
University of Waterloo
$34,000.00
Theoretical foundation of sublinear-time algorithms
EF 2020-21
Résumé
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.
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
RGPIN-2015-03907
Name nom
Blais, Eric
Department département
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
2020
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
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Installment
inst:6-7
Partie
2
Nb partie
7
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.