ANALYSIS of ALGORITHMS [RN 01-98]

Research News, January 1998

Previous News

Next News

Return to Research News Index

These pages are edited by Philippe.Flajolet@inria.fr.

Issue of January 1998.

[20/01/98] Princeton Meeting on "Average-Case Analysis of Algorithms", July 20-24, 1998. This is the fourth meeting specifically dedicated to Analysis of Algorithms. (The previous ones have been held in Schloss Dagstuhl in 1993, 1995, and 1997.) There, we should expect to hear quite a few interesting things regarding average-case and probabilistic analysis of algorithms, as well as corresponding properties of random structures. Here's an excerpt from the official announcement.

Announcement

The Fourth International Seminar on Average-Case Analysis of Algorithms

The Fourth International Seminar on Average-Case Analysis of Algorithms, sponsored by the DIMACS Special Year on Massive Data Sets, will take place July 20--24, 1998 at Princeton University, Princeton, New Jersey, USA.

This is the fourth in an ongoing series of meetings on the analysis of algorithms, which have been held in Dagstuhl, Germany, in the past and are planned for Barcelona and other locations in the future. The 1998 meeting is intended to attract more researchers from the U. S. to the field of analysis of algorithms.

The Organization Committee

Philippe Flajolet, France
Rainer Kemp, Germany
Hosam M. Mahmoud, U.S.A.
Helmut Prodinger, Austria
Robert Sedgewick, U.S.A.
Wojciech Szpankowski, U.S.A.

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:
-- Properties of large randomly-formed data structures
-- Analytic tools for analysis of algorithms
-- Probabilistic methods for analysis of algorithms
-- Combinatorial methods for analysis of algorithms
-- New results concerning average-case analysis of classical or new algorithms
-- Data compression and language-modeling methods
-- Behavior of algorithms under massive data sets

Atmosphere

Following the tradition of the first three seminars, the workshop 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. Speakers will be given a choice between 1/2 hour and 1 hour talks (allowing a period of discussion within each talk). A problem session will also be planned.

Also, following the tradition of previous seminars, we expect to organize a special issue of Algorithica to report on the results presented at the seminar.

This workshop is sponsored by DIMACS, in conjunction with the Special Year on Massive Data Sets.

We did not feel ready yet for a conference with programme committee and such. As a consequence, we have set up a list of invited speakers. Everybody is of course most welcome to attend! I'll report news soon about people that agree to participate.