# 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.