Skip to main content Skip to navigation

Randomised Algorithms

The area of Randomised Algorithms deals with the design and analysis of efficient algorithms that use randomness in their execution. A typical randomised algorithm uses uniformly random bits as an auxiliary input to guide its behaviour. The running time and the output are then random variables determined by the random bits chosen. The main benefit of using random bits is that it often achieves an improvement in the performance of the algorithm, for example, by avoiding certain worst-case configurations.

In the last two decades we have observed an explosive growth of interest in the area of randomised computations. Starting in the late 70s as a powerful tool in computational number theory, randomised algorithms are currently recognized as a very important and successful approach towards implementing efficient algorithms in theory and practice. The main advantages of the use of randomized algorithms is their usual simplicity and speed. For many applications, a randomised algorithm is the simplest algorithm available, or the fastest, or both (typical examples include QuickSort, a very efficient randomised sorting algorithm, or randomised schemes for hashing used frequently in sequential and distributed computations). However, while a randomised algorithm may be simple to implement (or perhaps just simpler than its deterministic counterparts), it is often challenging to provide a detailed and tight analysis of its behaviour.

The research of DIMAP in the area of randomised algorithms aims to make progress in our understanding of basic properties of randomised algorithms. This is achieved by providing mathematical analyses of fundamental techniques underlying randomised processes used by randomised algorithms. Sample problems of our interest include the study of various randomised allocation schemes (e.g., contention resolution protocols), randomised clustering algorithms, randomised load balancing processes, analysis of properties of basic stochastic processes and Markov chains, etc.

 

Sample publications: