# 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!)