I occasionally enjoy Thai cooking, so I appreciated some of the comments made by Andy Ricker.

I recently learned about India’s Clean Currency Policy which went into effect this year. I still have some money (in an unpacked box, probably) from my trip this last fall, and I wonder if any of it will be still usable when I go to SPCOM 2014 this year. That sounded a bit crazy to me though, further investigation indicates that an internal circular leaked and it sounds like a more sensible multi-year plan to phase in more robust banknotes. My large-ish pile of Rs. 1 coins remains useless, however.

An Astounding Result — some may have seen this before, but it’s getting some press now. It’s part of the Numberphile series. Terry Tao (as usual) has a pretty definitive post on it.

Avi Wigderson is giving a talk at Rutgers tomorrow, so I thought about this nice lecture of his on Randomness (and pseudorandomness).

There’s been a lot of blogging about the MIT Mystery Hunt (if I wasn’t so hosed starting up here at Rutgers I’d probably blog about it earlier) but if you want the story and philosophy behind this year’s Hunt, look no further than the writeup of Erin Rhode, who was the Director of the whole shebang.

Last year I did a lot of flying, and as a result had many encounters with the TSA. This insider account should be interesting to anyone who flies regularly.

I’m at EPFL right now on my way back from a trip to India. My last work-related stop there was the Tata Institute of Fundamental Research, where I am working with Vinod Prabhakaran on some follow-up work to our ISIT paper this year on correlated sampling. TIFR has a lovely campus in Navy Nagar, right next to the ocean in the south of Mumbai. It’s a short walk across the lawn to the ocean:

The beach at TIFR, looking north to the haze-obscured skyline of Mumbai

The grounds themselves are pretty rigorously landscaped and manicured:

The main building seen across the lawn in front of the ocean.

Earlier in my trip I visited IIT-Madras, hosted by Andrew Thangaraj and Radha Krishna Ganti and IIT-Bombay, where I was working with Bikash Dey on extensions to some of our AVCs-with-delay work. It’s been a great trip and it’s nice to visit so many different schools. The challenges facing Indian higher education are very different than those in the US, and it’s a good change of perspective from my usual US-centric view of things. Maybe I’ll write more on that later.

But for now, I wanted to get back to some actual technical stuff, so I thought I’d mention something that came up in the course of my discussions with Vinod today. For a joint distribution $P(X,Y)$, Wyner defined the common information in the the following way:

$\mathsf{CI}(X;Y) = \min_{X--U--Y} I(XY ; U)$

One fun fact about the common information is that it’s larger than the mutual information, so $I(X;Y) \le \mathsf{CI}(X;Y)$. One natural question that popped up as part of a calculation we had to do was whether for doubly-symmetric binary sources we could have a bound like

$\mathsf{CI}(X;Y) \le \alpha I(X;Y)$

for some “nice” $\alpha$. In particular, it would have been nice for us if the inequality held with $\alpha = 2$ but that turns out to not be the case.

Suppose $(X,Y)$ and are a doubly-symmetric binary source, where $Y$ is formed from $X \sim \mathsf{Bern}(1/2)$ by passing it through a binary symmetric channel (BSC) with crossover probability $\alpha$. Clearly the mutual information is $I(X;Y) = 1 - h(\alpha)$. For the common information, we turn to Wyner’s paper, which says $\mathsf{CI}(X;Y) = 1 + h(\alpha) - 2 h( \frac{1}{2}( 1 - \sqrt{1 - 2 \alpha} ) )$, which is a bit of a weird expression. Plotting the two for $\alpha$ between 0 and 1/2 we get:

Mutual and Common Information for a DSBS

If we plot the ratio $\mathsf{CI}(X;Y)/I(X;Y)$ versus $\alpha$, we get the following:

Ratio of Common to Mutual Information for a DSBS

The ratio blows up! So not only is Common Information larger than mutual information, it can be an arbitrarily large factor larger than the mutual information.

It might seem like this is bad news for us, but it just made the problem we’re working on more interesting. If we get any results on that I might be less engimatic and blog about it.

I was in New York on Sunday afternoon and on the suggestion of Steve Severinghaus we took a trip to the brand-new Museum of Mathematics, which is a short walk from the Flatiron building.

The Museum of Mathematics

It’s a great little place to take kids — there are quite a few exhibits which illustrate all sorts of mathematics from recreational math and Martin Gardner-esque pastimes like tessellations to an interactive video-floor which draws minimum distance spanning trees between the people standing on it. It apparently does Voronoi tessellations too but it wasn’t in that mode when I was there. There’s also a video wall which makes your body into a tree fractal, games, and a car-racing game based on the brachistochrone problem. The kids were all over that so I just got to watch.

One of the nice things was that there was a touch-screen explanation of each exhibit from which you could get three different “levels” of explanation depending on how much detail you wanted, and also additional information and references in case you wanted to learn more. That’s good because I think it will let parents learn enough to help explain the exhibit to their kids at a level that the parents feel comfortable. That makes it a museum for everyone and not just a museum for math-y parents who want to indoctrinate their children. On the downside, a lot of the exhibits were broken or under repair or under construction, so we really only got to see about 2/3 of the things.

Apparently it’s also a good place to go on a first date, as evidenced by some surreptitious people-watching. So if you’re in New York and want a romantic or educational time (aren’t they the same thing?), go check it out!

Bon voyage and safe travels to all those headed to St. Petersburg for ISIT 2011. Perhaps Max will blog about it, since I am not going to attend. Or if any of you see Alex, maybe you can convince him to contribute a post or two here…

I am visiting India, so I will probably not post too much for the month. Assuming I don’t get eaten alive by the mosquitoes (a distinct possibility), I’ll post more in December.

Maybe I’ll post a wedding photo or two (not my wedding).

Due to extensive traveling around. At the end of August and beginning of September I attended a workshop at the American Institute of Mathematics on Permanents and modeling probability distributions. It was a lot of fun, and a lot different than any workshop I’d been to before. There were only 20 or so participants and every day we’d break out in smaller groups to actually work on some sub-problem or area. By the end of the week I felt like I’d had a crash course in large-alphabet probability estimation and also got a sense of the huge range of problems and techniques (from exchangeable random partition processes to Markov chain Monte Carlo) involved in tackling them.

Last week I gave a talk on gossip algorithms at UC Davis and got a chance to talk with a lot of people there. It was a great trip, except for the 6:30 flight time out of San Diego. Then last weekend there were heirloom tomatoes:

Heirloom Tomato with bread and Cowgirl Creamery Red Tail cheese

And also peach pie:

Peach pie...

Mmmm, pie.

After ISIT I went to visit the Electrical Engineering Department at the University of Washington. I was invited up there by Maya Gupta, who told me about a little company she started called Artifact Puzzles.

On the research end of things, I learned a lot about the the learning problems her group is working on and their applications to color reproduction. I also got a chance to chat with Maryam Fazel about rank minimization problems, Marina Meilă about machine learning and distance models for rankings (e.g. the Fligner-Verducci model), and David Thorsley about self-assembling systems and consensus problems. All in all I learned a lot!

On the social side I got to hang out with friends in Seattle and UW and hiked for an afternoon at Mt. Ranier. Photos are on Picasa!

I’m at ISIT 2009 now at the COEX Center. Korea is pretty good so far (pictures to be posted later). The conference started today with a plenary by Rich Baraniuk, who talked about compressed sensing. I’d seen parts of the talk before, but it’s always nice to hear Rich speak because he’s so passionate about how cool the thing is.

I’ll try to blog about talks that I saw that were interesting as time permits — this time I’ll try to reduce the delay between talks and posts!

Just as I started blogging more, I’m going to take a break for a family vacation. In the meantime, I put up some more photos from Hong Kong and Rio de Janeiro on my Picasa album.

I’ve had two good dinners already here (for those who are meat eaters). I should hit the gym to convert all the protein into muscle! The first was at Via Sete, which has pretty tasty appetizers, salads, and grilled meats and fish. We got some crab cakes (bolinhos) and calamari with manioc flour batter (it’s much soggy than normal fried calamari). I had a salad with grilled meat which was delicious (and also not too heavy, which was nice). The next dinner was at Braseiro de Gávea, a more traditional Brasilian restaurant. It was packed and the food was delicious — you basically order a set of grilled meat and it comes with one zillion side dishes (like farofa with eggs and banana, surprisingly delicious). I didn’t get to take pictures, but I might add them in later. Note : one dish serves about 3.5 people, so 3 dishes was waaaay too much food for the 7 of us. Afterwards we hit up the Academia de Cachaça, which was appropriate since some of us were in academia. They have a crazy array of cachaças to try in a pleasant open-air environment.