The SPAMS Schedule - Spring 2010

Abstract: There is an interesting connection between random walks on graphs and electric flows. Specifically, if we think of the graph G as a network of nodes and wires, and the wires have unit resistance, then several properties of the random walk on G can be interpreted in terms of effective resistances between pairs of vertices. We will survey some of the connections, and, time permitting, show where they have come up in recent algorithmic work.

This talk should be accessible to a broad audience.

The simplex algorithm for solving linear programming problems was introduced by George Dantzig in 1947, and is recognized to be one of the 10 most influential algorithms of the 20th century. It is also one of the most controversial ones. This talk will present some aspects of the controversy, starting from a simple presentation of the simplex algorithm. In particular, I will touch upon issues of cycling, worst-case exponential behavior, average-case behavior and smoothed complexity, and numerical stability. I will conclude with a curious conjecture.

Note: a good knowledge of linear algebra is required to appreciate the details.

Ever wondered how your spam filter works (or doesn't)? Inspired by the name of this seminar series and an Olympic skier known as the "spam king," I'll tell you everything interesting I can learn about the subject.

Iterative maps often arise in the study of dynamical systems. Applying a map consecutively to an initial point defines a sequence, and consequently one is often interested in understanding its long time evolution. If the map is chaotic, the sequence samples an appropriate space with some probability measure. A natural problem is therefore to determine the measure for a predetermined iterative map. In addition, motivated by the practical problem of sampling from a random distribution, the inverse problem also arises: how to find the iterative map from a probability distribution. I will discuss these problems and construct some solutions.

Abstract: In this talk, I explore the many connections between computer science, analysis, probability, combinatorics, algebra, number theory, and Indian cinema. Of particular interest will be both research problems arising from film and the use of film as a pedagogic aid. Examples of both types will be provided, with subtitles.

Note: This talk is a revision of a talk given last year. It will have roughly the same plot as the original, but many more songs and teary monologues by white-haired mothers. In other words, it's the Bollywood remake.