Grant: Discovery Grants Program - Individual
University of Victoria
$20,500.00
Randomness and complexity
FY 2010-11
Summary
This research program studies the strengths and limitations of randomized algorithms in various computational settings. A randomized algorithm is an algorithm that has access to a source of random bits and uses it as an auxiliary input to guide its behaviour. During the last two decades, understanding the role of randomness in computation has been an fascinating area of research leading to several fundamental results.
It is now well known that randomized algorithms are capable of performing some computational tasks much more efficiently than known deterministic algorithms in specific settings, even those that are impossible deterministically. There is also good evidence that randomization does not give additional power in a general setting.
However, our understanding of the true power of randomness as a resource is still far from complete. The goal of this proposal is to further explore the power of randomness in various computational models and to find new applications of these results to other areas of computer science.
Program
Discovery Grants Program - Individual
Recipient
Location
British Columbia, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
283327-2007
Name nom
Srinivasan, Venkatesh
Department département
Computer Science
Organization id
7
Institution établissement
University of Victoria
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2007
Award amount
20500
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1200
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Advancement of knowledge
Area of application fr
Avancement des connaissances
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
4
Nb partie
5
Application title
Randomness and complexity
Keyword
NSERC
Application summary
This research program studies the strengths and limitations of randomized algorithms in various computational settings. A randomized algorithm is an algorithm that has access to a source of random bits and uses it as an auxiliary input to guide its behaviour. During the last two decades, understanding the role of randomness in computation has been an fascinating area of research leading to several fundamental results.
It is now well known that randomized algorithms are capable of performing some computational tasks much more efficiently than known deterministic algorithms in specific settings, even those that are impossible deterministically. There is also good evidence that randomization does not give additional power in a general setting.
However, our understanding of the true power of randomness as a resource is still far from complete. The goal of this proposal is to further explore the power of randomness in various computational models and to find new applications of these results to other areas of computer science.