Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Simon Fraser University

$29,000.00

Analysis of Randomized Algorithms

FY 2009-10

Summary
The proposed research program is in Theoretical Computer Science. It is mainly concerned with the design and analysis of algorithms, and here, in particular, randomized algorithms, and algorithms for dynamic systems (like dynamic load balancing processes and dynamic routing problems in networks). The main goals of this program are (i) to apply formal methods and techniques to real-world problems, e.g., in Networking (computer-related or otherwise), or in Biology, in a rigorous way, and(ii) to advance the formal (i.e., mathematical) methods and techniques used to study these models. One main vehicle that is going to be used is that of randomized algorithms and their probabilistic analysis, or sometimes ``just'' the probabilistic analysis of structures used to model certain phenomena/scenarios. Randomized algorithms are typically a very elegant and efficient way of solving problems that would otherwise be very hard (or even impossible) to solve. An example would be Property Testing, which is about devising and analyzing algorithms that verify whether or not a certain object (e.g., a database, or a DNA string) has a certain property. Randomized algorithms can do that in time that is sub-linear in the size of the object, i.e., even without looking at all parts of the object (one must allow for a certain error probability though).
Program
Discovery Grants Program - Individual
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
250284-2007
Name nom
Berenbrink, Petra
Department département
Computing Science
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2009
Competition year année de concours
2007
Award amount
29000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
805
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
Communications technologies (satellites, radar, etc.)
Area of application fr
Technologie des télécommunications (satellites, radar,etc.)
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
3
Nb partie
5
Application title
Analysis of Randomized Algorithms
Keyword
NA
Application summary
The proposed research program is in Theoretical Computer Science. It is mainly concerned with the design and analysis of algorithms, and here, in particular, randomized algorithms, and algorithms for dynamic systems (like dynamic load balancing processes and dynamic routing problems in networks). The main goals of this program are (i) to apply formal methods and techniques to real-world problems, e.g., in Networking (computer-related or otherwise), or in Biology, in a rigorous way, and(ii) to advance the formal (i.e., mathematical) methods and techniques used to study these models. One main vehicle that is going to be used is that of randomized algorithms and their probabilistic analysis, or sometimes ``just'' the probabilistic analysis of structures used to model certain phenomena/scenarios. Randomized algorithms are typically a very elegant and efficient way of solving problems that would otherwise be very hard (or even impossible) to solve. An example would be Property Testing, which is about devising and analyzing algorithms that verify whether or not a certain object (e.g., a database, or a DNA string) has a certain property. Randomized algorithms can do that in time that is sub-linear in the size of the object, i.e., even without looking at all parts of the object (one must allow for a certain error probability though).