Grant: Discovery Grants Program - Individual
University of Calgary
$23,000.00
Applications of probabilistic methods to algorithms and complexity
FY 2012-13
Summary
Probabilistic methods belong to the most important tools in theoretical computer science. While the design of efficient randomized algorithms is one of the obvious applications, probabilistic methods are also extensively used in other areas, such as combinatorics or in complexity theory. In this research program, I intend to develop and apply probabilistic methods in three areas of theoretical computer science.
(1) Algorithms: For hashing and dictionary problems, there is a gap between the type of algorithms that are used in practice and algorithms that have good theoretical properties. The best randomized dictionaries provide lookup and update operations in constant time (with high probability). But often the constants in the time and space bounds are huge, or the algorithms are too complicated to be accepted in practice. My goal is to find simpler algorithms, mainly for hashing applications, that have good running time guarantees, but where the constant factors in time and space are such that the algorithms become interesting for practical purposes.
(2) Distributed Computing: Problems on asynchronous shared memory models have been studied extensively, but with respect to randomized computation, many questions still remain unanswered. On the other hand, probabilistic methods seem to be a suitable tool to overcome the problems associated with asynchrony. My goal is to devise new randomized shared memory algorithms for selected problems such as mutual exclusion, or the simulation of strong atomic operations by weaker ones.
(3) Complexity Theory: The ""number on forehead"" multiparty communication model is an important computation model, that is not well enough understood. Good lower bounds in this model would have significant consequences for circuit, propositional proof, or branching program complexity. I intend to apply probabilistic methods, especially those based on universal hash families, in order to develop better lower bound methods and to gain a better understanding of the multiparty communication model.
Program
Discovery Grants Program - Individual
Recipient
Location
Alberta, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
356080-2008
Name nom
Woelfel, Philipp
Department département
Computer Science
Organization id
11
Institution établissement
University of Calgary
Province en
Alberta
Province fr
Alberta
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2008
Award amount
23000
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
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
5
Nb partie
5
Application title
Applications of probabilistic methods to algorithms and complexity
Keyword
NSERC
Application summary
Probabilistic methods belong to the most important tools in theoretical computer science. While the design of efficient randomized algorithms is one of the obvious applications, probabilistic methods are also extensively used in other areas, such as combinatorics or in complexity theory. In this research program, I intend to develop and apply probabilistic methods in three areas of theoretical computer science.
(1) Algorithms: For hashing and dictionary problems, there is a gap between the type of algorithms that are used in practice and algorithms that have good theoretical properties. The best randomized dictionaries provide lookup and update operations in constant time (with high probability). But often the constants in the time and space bounds are huge, or the algorithms are too complicated to be accepted in practice. My goal is to find simpler algorithms, mainly for hashing applications, that have good running time guarantees, but where the constant factors in time and space are such that the algorithms become interesting for practical purposes.
(2) Distributed Computing: Problems on asynchronous shared memory models have been studied extensively, but with respect to randomized computation, many questions still remain unanswered. On the other hand, probabilistic methods seem to be a suitable tool to overcome the problems associated with asynchrony. My goal is to devise new randomized shared memory algorithms for selected problems such as mutual exclusion, or the simulation of strong atomic operations by weaker ones.
(3) Complexity Theory: The ""number on forehead"" multiparty communication model is an important computation model, that is not well enough understood. Good lower bounds in this model would have significant consequences for circuit, propositional proof, or branching program complexity. I intend to apply probabilistic methods, especially those based on universal hash families, in order to develop better lower bound methods and to gain a better understanding of the multiparty communication model.