https://www.dagstuhl.de/9124

10. – 14. Juni 1991, Dagstuhl-Seminar 9124

Randomized Algorithms

Organisator

M. Karpinski, M. Luby, U. Vazirani

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team

Dokumente

Dagstuhl-Seminar-Report 14

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!

Dagstuhl-Seminar Series

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.