Linkage (and a puzzle)

I saw Scott’s talk today on some complexity results related to his and Alex Arkhpov’s work on linear optics. I missed the main seminar but I saw the theory talk, which was on how hard it is to approximate the permanent of a matrix X whose entries (X_{ij}) are drawn iid complex circularly-symmetric Gaussian \mathcal{CN}(0,1). In the course of computing the expected value of the 4th moment of the permanent, he gave the following cute result as a puzzle. Given a permutation \sigma of length n, let c(\sigma) be the number of cycles in \sigma. Suppose \sigma is drawn uniformly from the set of all permutations. Show that

\mathbb{E}[ 2^{c(\sigma)}] = n + 1.

At least I think that’s the statement.

In other news…

  • Ken Ono has announced (with others) an algebraic formula for partition numbers. Very exciting!
  • Cosma thinks that New Yorker article is risible, but after talking to a number of people about it, I realized that the writing is pretty risible (and that I had, at first pass, skimmed to the part which I thought was good to report in the popular (or elitist) press, namely the bias towards positive results. Andrew Gelman points out that he has written about this before, but I think the venue was the more interesting part here. What was risible about the writing is that it starts out in this “ZOMG OUR SCIENCE POWERZ ARE FAAAAAAADINNNNNNGGGGGGG,” and then goes on to say slightly more reasonable things. It’s worthy of the worst of Malcolm Gladwell.
  • Tofu is complicated.
  • The 90-second Newbery contest.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.