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:

• M. Adamaszek, A. Czumaj, and C. Sohler. Testing Monotone Continuous Distributions on High-dimensional Real Cubes. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms (SODA'10), pages 56 - 65, 2010.
• A. Czumaj and C. Sohler. Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM Journal on Computing, 39(3): 904 - 922, August 2009.
• A. Czumaj A. Shapira, and C. Sohler. Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM Journal on Computing, 38(6): 2499 - 2510, April 2009 (also SODA'07).
• A. Czumaj and C. Sohler. Testing Expansion in Bounded-Degree Graphs. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), pages 570 - 578, 2007.
• A. Czumaj and C. Sohler. Sublinear-time Algorithms. Bulletin of the EATCS, 89: 23 - 47, 2006.
• P. Berenbrink, A. Czumaj, A. Steger, and B. Vöcking. Balanced Allocations: The Heavily Loaded Case. SIAM Journal on Computing, 35(6): 1350 - 1385, 2006.
• A. Czumaj and W. Rytter. Broadcasting Algorithms in Radio Networks with Unknown Topology. Journal of Algorithms, 60(2): 115 - 143, August 2006.
• L. A. Goldberg, R. A. Martin, and M.S. Paterson. Strong Spatial Mixing with Fewer Colors for Lattice Graphs. SIAM Journal on Computing, 35(2): 486 - 517, 2005.
• L. A. Goldberg, M. Jerrum, S. Kannan, and M.S. Paterson. A Bound on the Capacity of Backoff and Acknowledgement-based Protocols. SIAM Journal on Computing, 33(2): 313 - 331, 2004.
• M. Adler, H. Räcke, N. Sivadasan, C. Sohler, and B. Vöcking. Randomized Pursuit-Evasion in Graphs. Combinatorics, Probability & Computing, 12(3): 225 - 244, 2003.
• L. A. Goldberg, P. D. MacKenzie, M.S. Paterson, and A. Srinivasan. Contention Resolution with Constant Expected Delay. Journal of the ACM, 47(6): 1048 - 1096, 2000.
• A. Czumaj and M. Kutylowski. Delayed Path Coupling and Generating Random Permutations. Random Structures and Algorithms, 17(3-4): 238 - 259, 2000.