Greetings from ICML 2014

The famous “bird nest”

Greetings from ICML 2014! I will attempt to blog the conference in between attending sessions, giving my talk and poster, and stressing out about writing my CAREER award. Despite what Google Maps might tell you, my hotel is not across the street from the stadium pictured above — this led to a rather frustrating 30 minutes of walking around asking for directions. I do, however, have a lovely view from my room of the Bank of Communications (交通银行), which seems appropriate, somehow.

I can’t access Facebook or Twitter from China without some crazy paid VPN solution it seems (if you have any tips, feel free to email me), so I don’t know if this post will even make it to those services. It’s probably for the best — social media is too much of a distraction, right?

Documents needed for a Chinese Tourist Visa

I just got a tourist visa (L) to go to ICML from the Chinese Consulate in New York, and it was significantly less difficult than I had been led to believe. However, the information on the website is a little hard to parse (since there are so many visa classes), so here’s a quick list of the documents you need:

• Passport with at least six months of remaining validity and blank page for the visa.
• A photocopy of passport photo and information page.
• Copy of the application form with 1 passport photo attached.
• Printout of your plane ticket confirmation and hotel booking confirmation \textbf{OR} a formal invitation letter. The hotel need not be for the entire duration of your trip.

You will need to make two trips, the first to drop off the forms and your passport, and the second (4 days later) to pick up your passport and pay (currently \$140). A tip that holds for New York (and probably elsewhere): don’t go right at opening time, since there is a huge rush. The line tends to thin between 10 and 11, and your wait will be significantly shorter. Depending on how annoyed the guards are, they may yell at you for using your phone (technically not allowed), so bring a magazine or some knitting or something in case the wait is long. When you pay, it’s MasterCard/Visa only, or cashiers check/money order.

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.

Bounds between common information and mutual information

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.

Mo’ math, mo’ solutions

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!

Safe travels to ISIT 2011

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…

Hiatus

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).