The Behavior of Algorithms

18.409 Topics in Theoretical Computer Science

Instructor: Dan Spielman.

Tuesday/Thursday 2:30-4:00 in 3-270

In this course, we will discuss rigorous approaches to explaining the typical
performance of algorithms.  In particular, we examine alternatives to the
traditional worst-case and average-case analyses.  Such analyses must
necessarily make assumptions about the inputs to algorithms.

We will develop this theory together, and I expect we will debate the merits of
various approaches, as well as the names I have tentatively assigned to them.

My lectures will center around the following three approaches.

 1. smoothed analysis:
       Analyzing algorithms assuming their inputs are subject to noise.  That
       is, we measure the maximum over inputs of the expected performance of
       an algorithm under slight random perturbations of those inputs.  This
       is the intersection of Shannon Theory with Analysis of Algorithms by
       assuming inputs come through a noisy channel.

 2. condition numbers/parametric analysis:
     In this approach, we find a simple parameter of the input that is
     predictive of the running time of the algorithm.  This parameter should
     be significtanly simpler than "the running time of the algorithm".
     Examples could include 
        a. feature size of point sets,
        b. condition numbers of matrices or polynomials,
        c. bit length of inputs

 3. subclassing inputs:

     In many practical problem domains, the inputs to algorithms have special
     structure, and may form a proper subclass of the possible inputs.  If it
     is known an algorithm in a particular application only see inputs from this
     subclass, then it is natural to analyze the performance of this algorithm
     on the subclass.

Students will perform class projects examining the applicability of these
analyses to some problem area, and will present their findings to the class as
well as writing up their findings. Some students may wish to choose their
project from a list of tractable open problems that will be circulated within
the class.

Students will also be responsible for scribing lectures.

Prerequisites: At least one graduate course in algorithms or numerical analysis.
Enrollment may be limited.