Title: Probabilistic Transforms in the Analysis of Algorithms

Speaker: 
Kevin J. Compton
EECS Department
University of Michigan
Ann Arbor


Date: Friday, March 2,2007
Time 11-12PM
Venue: Room 3464, HKUST

  
Abstract:
(Joint work with Olgica Milenkovic and Jonathan Brown)

In probability theory, the Poisson approximation is a well
known technique based on the observation that
under certain circumstances, a binomial distribution is very
close to a Poisson distribution.  The substitution of
a Poisson distribution for a binomial distribution sometimes
simplifies problems.  One way to make this substitution
rigorous is to define a probabilistic transform
called the Poisson transform.  This is really a method for
averaging statistics on a family of discrete probabability
spaces.  The Poisson transform and its inverse transform
have been very useful in the analysis of various algorithms
in computer science, e.g., hashing algorithms.

In this talk we show the Poisson transform is just one
of many probabilistic transforms useful to the analysis
of algorithms.  One of the keys to using these transforms
is to find inverse transorms which allow us to translate
results in the transformed space back to the original problem.
We will give examples of several different kinds of
probabilistic transforms and show how they can be used
to do an average-case analysis of algorithms for presorting,
merging lists, and computer algebra.