Feb 18 Alex Levin

Random Walks and Electric Networks

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.

Feb 25 Leonid Chindelevitch

Simplex: a simple algorithm

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.

Mar 4 Po-Ru Loh

Spam @ SPAMS

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.

Mar 11 David Shirokoff

Measuring the use of Chaotic Maps

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.

Mar 18 Amanda Redlich

Math and Indian Popular Cinema

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.

Apr 8 Anand Oza

Non-locality (Spookiness) in Quantum Theory

Apr 15 Alejandro Morales

Rook placements, matrices over finite fields and starry night

Apr 22 Mark Lipson

Modularity and Evolution

May 6 Martina Balagovic

Wang Tiles