June 10 – 14 , 1991, Dagstuhl Seminar 9124

Randomized Algorithms


M. Karpinski, M. Luby, U. Vazirani

For support, please contact

Dagstuhl Service Team


Dagstuhl-Seminar-Report 14


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!

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.