TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 9124

Randomized Algorithms

( Jun 10 – Jun 14, 1991 )

Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/9124

Organizers
  • M. Karpinski
  • M. Luby
  • U. Vazirani



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!

Copyright

Participants
  • M. Karpinski
  • M. Luby
  • U. Vazirani

Related Seminars
  • Dagstuhl Seminar 01231: Design and Analysis of Randomized and Approximation Algorithms (2001-06-03 - 2001-06-08) (Details)
  • Dagstuhl Seminar 05201: Design and Analysis of Randomized and Approximation Algorithms (2005-05-15 - 2005-05-20) (Details)
  • Dagstuhl Seminar 08201: Design and Analysis of Randomized and Approximation Algorithms (2008-05-11 - 2008-05-16) (Details)
  • Dagstuhl Seminar 11241: Design and Analysis of Randomized and Approximation Algorithms (2011-06-13 - 2011-06-17) (Details)