Randomized Algorithms

Summary

This Workshop was concerned with the newest development in the design of efficient (both sequential and parallel) randomized and pseudo-randomized algorithms as well as with the foundations of complexity theory of the randomized computation. The advantages of using randomization in the design of algorithms have been increasingly evident in the last couple of years. For some computational tasks it appears now that these algorithms are more efficient than the purely deterministic ones (in terms of the running time, hardware size, circuits depth, etc.). The very striking examples recently were the new randomized algorithms for enumerating the number of perfect matchings in certain classes of graphs or for some enumeration problems in the boolean algebra and finite fields. Solutions to these problems have applications ranging from the circuit design and coding theory to statistic mechanics and quantum field theory. The problem of deterministic simulation of certain classes of randomized algorithms and circuits was also another topic of this workshop.

The 34 participants of the workshop came from nine countries, eleven of them came from North America. The 24 lectures covered a wide body of research in randomized algorithms. Abstracts of the talks are listed in the next section.

The meeting was hold in a very informal and stimulating atmosphere. Thanks to everybody in Dagstuhl who made this workshop so interesting and enjoyable!