University Homepage School Homepage School Contacts School Search

The Algorithmic Power of Randomness

Mary Cryan
2 pm, Thursday 20 May

A small amount of randomness can often be very useful in designing all sorts of algorithms. This is especially true when we focus on counting problems, where we want to design an algorithm to approximately count the elements of some set of combinatorial structures of interest to us. Apart from a few simple examples, all of the approximate counting algorithms for #P-complete problems (the "difficult" counting problems) are randomized algorithms.

In my talk I will mention a couple of interesting open problems in approximate counting which I am currently working on. I will give a very basic explanation of two powerful but simple randomized techniques which may be useful for solving these problems - the Markov chain Monte Carlo method, and the "dart-throwing" method.

I'll also touch on another issue - the question of why there are
(virtually) no deterministic approximation algorithms for #P-complete
counting problems. This is very different to the situation for standard
approximation problems. Is Randomness really so powerful in the context of counting? This question is very open at the moment.

This will be a very general introductory talk.