FOCS Second Day

On Sunday morning there were two presentations about algorithms to learn mixtures of Gaussian distributions. If one has a mixture of k Gaussian distributions on the plane (that is, a distribution in which, with probability p_i we sample from a Gaussian distribution G_i, for i=1,\ldots,k), then after we take several samples from such a distribution we will see k fuzzy ellipses, corresponding to the k Gaussians, which will be more or less dense depending on the p_i. One can then eyeball what are centers of the ellipses, corresponding to the averages of the Gaussians, what are the directions and lengths of the axes, corresponding to the standard deviations, and what are the densities, corresponding to the p_i. As for several geometric problems that are very simple in one or two dimensions, the known methods to reconstruct the Gaussians from samples had complexity growing, in general, exponentially with the number of dimensions. It was possible to do better if the typical regions occupied by the Gaussians are disjoint, in which case a good clustering algorithm will correctly classify, for most points, to which Gaussian it belongs to, and then the parameter of the Gaussian are easily inferred. The papers of Moitra and Valiant and of Belkin and Sinha give algorithms that run in time polynomial in the number of dimensions even when the typical regions of the Gaussians overlap. The first paper uses a more constructive method; the second relies on quantifier elimination in the theory or real numbers, which is applied after a dimension-reduction argument, but it applies to a wider class of distributions, not just Gaussians.

In the last talk of the day, Toni Pitassi gave a very moving talk remembering Avner Magen, the Toronto University professor who recently died in a climbing accident. Toni alternated personal memories, from her and others, with technical material. She gave a very vivid picture of a person that I never met, but that I definitely wish I had.

I then attended a dinner meeting of the FOCS Mafia. I am not at liberty to reveal what backroom deals we agreed to, other than to say that we literally ate in a backroom.

At the business meeting, it was decided that there will be no more printed proceedings. I am bit saddened by it, but at least I am relieved that the topic will never again be raised in a business meeting. We will have to make do with discussing whether or not to go back to a single-session format. I violated my own rules and spoke for a little more than five minutes. This didn’t matter because not only there was beer, but also wine, which we were encouraged to finish because it was already all paid for.

Traditionally, when a conference is held at a hotel, the hotel upgrades the conference chair to a suite. I had arrived being quite excited about what a “suite” might be in a Vegas hotel, having expectations of a place with leopard prints on the wall, a hot tub in the middle of the room, maybe a stripper pole, the kind of place where one might wake up with a dead stranger and a tiger (I think I am mixing up two movies here). Instead it was just a regular room but bigger, and with a sitting area. It was enough for a group of theoreticians to sit down after the business meeting, drink leftover wine, and talk about their young children. (Yay Las Vegas debauchery!)


First Day of FOCS

FOCS 2010 is held at the Monte Carlo hotel in Las Vegas (yay randomized algorithms jokes!), which is next to the City Center, an unfortunately timed new development with a beautifully designed hotel, condos, and a shopping center with all the usual expensive firms (Hermes, Prada, LV, …) and some remarkable ones (Balenciaga!). The architecture is playful, modern and tasteful, the scale is rather grand, everything is very clean. I surprise myself thinking, this looks like Asia.

Talking about which, I finally found a place where coffee is more expensive than in Beijing: $3+ for an espresso at Starbucks.

Ketan Mulmuley did a great job with his tutorial. Even I, that knew nothing whatsoever about his program to proving circuit lower bounds via algebraic geometry and representation theory, got quite a bit out of it.

At night, I take a cab with another theoretician. “We are going to Double Down.” “You know” says the driver “you have to be careful around there.” “Careful? is it an unsafe area?” “No, no, it’s just that Double Down is the only bar in that area that…” The driver gives a good look at the two us in the rearview mirror and starts again: “… All the other bars in the area are for the ‘alternative lifestyle’…” He gives us another look. “Unless that’s what you are looking for… Which is cool… But then don’t go to Double Down, because it’s the only straight bar over there.” I want to explain to him that my friend is not gay, he is just Israeli, but we have arrived and we’ll have to have that conversation another time.