Smoothed Analysis Day at CWI: February 26, 2010

The overall performance of an algorithm is usually assessed by its worst-case complexity, i.e., the performance of the algorithm on a worst possible input instance. However, this viewpoint is overly pessimistic in many situations since worst-case instances might correspond to artificially constructed instances that rarely occur in practice.

Spielman and Teng introduced smoothed analysis as a means to overcome the overly pessimistic viewpoint adopted in worst-case analysis. The basic idea is simple: Given an input instance, randomly perturb the input values and analyze the expected worst-case performance of the algorithm on the perturbed instances. If worst-case instances are "fragile'' to random perturbations the smoothed complexity of the algorithm is usually much lower than its worst-case complexity.

In a seminal paper, Spielman and Teng proved that the simplex method with a certain pivot rule has polynomial smoothed complexity (while its worst-case complexity is exponential). Daniel Spielman maintains a smoothed analysis website where he collects results related to smoothed analysis; please refer to this website for further information.

We are organizing a Smoothed Analysis Day at the Center for Mathematics and Computer Science (CWI) in Amsterdam. The idea is to have five presentations and leave sufficient time for discussions. The list of speakers is:

• Berthold Vöcking, RWTH Aachen, Germany
• Heiko Röglin, Maastricht University, The Netherlands
• Bodo Manthey, University of Twente, The Netherlands
• Tjark Vredeveld, Maastricht University, The Netherlands
• Guido Schäfer, CWI Amsterdam, The Netherlands

The meeting is kindly supported by the mathematics cluster DIAMANT.