Towards a Theory of Randomized Shared Memory Algorithms
Philipp Woelfel, University of Calgary
Randomization has become an invaluable tool to overcome some of the problems associated with asynchrony and faultiness. Allowing processors to use random bits helps to break symmetry, and to reduce the likelihood of undesirable schedules. As a consequence, randomized techniques can lead to simpler and more efficient algorithms, and sometimes to solutions of otherwise unsolvable computational problems. However, the design and the analysis of randomized shared memory algorithms remains challenging.
This talk will give an overview of recent progress towards developing a theory of randomized shared memory algorithms. It will demonstrate how random choices can be used to improve the efficiency of Las Vegas algorithms for fundamental problems, and report on recent attempts to devise space efficient Monte Carlo algorithms. It will also explain why modular algorithm design is much more difficult for randomized algorithms than for deterministic ones, and what we can do about it.
Biography: Philipp Woelfel is Canada Research Chair in Randomized and Distributed Algorithms in the Department of Computer Science at the University of Calgary. He received the dissertation award of the University of Dortmund, Germany, for his Ph.D. in 2003. Before joining the University of Calgary, he worked as a postdoctoral fellow at the University at the Toronto, funded by the “Emmy Noether” excellence program of the German Research Foundation. Dr. Woelfel has received funding for his research from the German Research Foundation, the NSERC Discovery grants program, Hewlett Packard, and the Canada Research Chair Program. In 2014 he received a prestigious NSERC Discovery Accelerator Supplement for his research program on randomized shared memory algorithms. His research has focused on complexity theory, randomized algorithms, and the theory of distributed computing.