DIMACS Workshop: The Fourth International Seminar on Average-Case Analysis of Algorithms

July 20 - 24, 1998
Princeton University, Computer Science Department
35 Olden Street, Princeton, NJ

Organizers:
Philippe Flajolet, INRIA philippe.flajolet@inria.fr
Rainer Kemp, Johann Wolfgang Goethe-Universitat kemp@sads.informatik.uni-frankfurt.de
Hosam Mahmoud, George Washington University, hosam@gwis2.circ.gwu.edu
Helmut Prodinger, Vienna University of Technology, Helmut.Prodinger@tuwien.ac.at
Robert Sedgewick, Princeton University, rs@cs.princeton.edu
Wojceich Szpankowski, Purdue University, spa@cs.purdue.edu

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.

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

The workshop is intended to provide participants with numerous opportunities for interaction and discussion, centered around a program of about 30 invited talks on recent research in the analysis of algorithms. A tentative program will be available prior to the meeting.

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

Contacts:

If you have technical questions about the scientific program, you may contact 
the main organizer at
 
 Hosam Mahmoud:             hosam@gwis2.circ.gwu.edu

Or you may also contact one of the other organizers at:

 Philippe Flajolet:         philippe.flajolet@inria.fr
 Helmut Prodinger:          Helmut.Prodinger@tuwien.ac.at  
 Reobert Sedgewick:         sedgewick@cs.princeton.edu
 Wojciech Szpankowski:      spa@cs.purdue.edu
 

If you have administrative or logistical questions, you may contact

  Sandy Barbu    barbu@cs.princeton.edu

The following is a list of prospective participants:

    Baeza-Yates, Ricardo  
    Bergeron, Francois
    Chen, Jin-Cheng
    Clement, Julien
    Coffman, Ed
    Compton, Kevin
    Condon, Ann
    Drmota, Michael
    Fill, James
    Flajolet, Philippe 
    Gardy, Daniele
    Gittenberger, Bernhard
    Golin, Mordecai        
    Grabner, Peter
    Hofri, Micha       
    Hwang, Hsien-Kuei
    Jelekovic, Predrag    
    Knopfmacher, Arnold
    Lent, Janice
    Liebehenschel, Jens
    Louchard, Guy      
    Mahmoud, Hosam
    Martinez-Parra, Conrado
    Miller, Victor
    Nebel, Markus
    Odlyzko, Andrew   
    Panario, Daniel
    Panholzer, Alois
    Pittel, Boris
    Poblete, Patricio
    Prodinger, Helmut
    Reingold, Edward
    Roura-Ferret, Salvador   
    Rueschendorf, Ludger
    Schmutz, Eric
    Sedgewick, Robert
    Smythe, Robert
    Soria, Michele
    Szpankowski, Wojciech
    Vallee, Brigitte
    Viola, Alfredo

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

Next: Call for Participation
Workshop Index
DIMACS Homepage
Contacting the Center
Document last modified on June 5, 1998.