Some Thoughts from SODA

There are many reports from SODA at the various theory blogs, but here's a quick report:

Persi Diaconis gave a great talk on interesting connections among carrying, shuffling, and Young tableaux. The starting point: consider adding m n-digit numbers, where the numbers are uniform base b. Then the possible carry values are between 0 and m - 1. For large n, what's the fraction of time the carry value is 0, 1, 2,... As the carries process is a Markov chain, this can be determined. He then connected this to theory of shuffles. Here's a nice model for a shuffle; each "card" corresponds to a point chosen uniformly on [0,1]. An a-shuffle maps x-> ax mod 1. The resulting re-ordering is a shuffling of the cards, which leads the way to analysis. From there he went on to tableaux.

Rather than try to summarize the talk, I'll point to his major references:

John Holt, Am Math Monthly: Carries, Combinatorics and an Amazing Matrix
Persi Diaconis, web page, papers from 2003: Mathematical developments from the analysis of riffle shuffles
R. Stanley: Volume II, enumerative combinatorics, chapter 7

He left open the problem of trying to develop a clean, pretty correspondence between the carrying process and shuffles.

Muthu conversed in the morning about MapReduce; see his new blog entry. In particular, the perspective and counterperspective on MapReduce in this post from the Database Column is quite entertaining.

I enjoyed the talk for (and want to understand the paper for) Improved Algorithmic Versions of the Lovasz Local Lemma by Aravind Srinivasan (who didn't give the talk, but it was still well-given). The Lovasz local lemma is quite beautiful, although I don't think I've ever used it in a paper. I'm inspired to try to find a good use for it.