Analysis of Algorithms
MSRI, California, USA
|
Design by Mariola Szpankowska |
|
This is the tenth seminar specifically dedicated to the
Analysis of Algorithms.
The previous meeting were held in Schloss Dagstuhl
(Germany) in 1993, 1995, and 1997, in Princeton (USA) in 1998, in
Barcelona (Spain) in 1999, Krynica Morska, Poland (2000),
Tatihou, France (2001), Strobl, Austria
(2002), and last year in San Miniato, Italy.
This year the seminar will held at the
MSRI.
The meeting is sponsored by MSRI.
Scope .
Predicting the performance of algorithms is a likely outgrowth of ongoing
research in analytic combinatorics and the analysis of random
discrete structures. This workshop will bring
together leading researchers in this field to focus on such problems.
Probabilistic considerations on inputs and the random combinatorial
structures underlying algorithmic analysis have provided an active
area of modern research. One assumes some
reasonable probability distribution on input instances to an
algorithm as a way of understanding the inner workings of the
algorithm and its "typical behavior." Experience in the field shows
that it is often unwieldy to work with exact models, where on
the other hand one can say something meaningful and precise on the
typical "asymptotic" behavior of the algorithm, when
either the underlying combinatorial structure becomes very large or
when the algorithm is challenged by massive data sets.
In these cases one sometimes gets simplified but exact
expressions dealing with first (or higher) order expansions of averages,
moments or distributions, as some parameters of the algorithmic
problem grow to be very large.
The focus of this workshop is the average case analysis of algorithms,
and its relation to the wider areas of analytic combinatorics,
exact and limiting distributions, formal techniques,
probability theory, combinatorics and computer science.
We identify the following areas as being of particular interest:
Atmosphere.
Following the tradition of the first four seminars, this seminar
intends to bring together leading researchers in the
Analysis of Algorithms and provide them with a relaxed atmosphere for
interaction and discussion. Therefore, the talks will generally
be brief and somewhat sparse. Long lunch breaks and one free
afternoon will be purposely planned. A problem session will
also be planned.
Persi Diaconis, Philippe Flajolet, Don Knuth, and
Dick Karp.
Philipe Jacquet, Helmut Prodinger, Gadiel Seroussi,
Robert Sedgewick, Wojtek Szpankowski (chair), Marcelo Weinberger,
and Brigitte Vallee