The Geomblog

Jeff Phillips and I organized a workshop on Geometry In The Field at SoCG 2012. I haven't blogged about the workshop yet because Jeff and I are working on a more detailed report for the SIGACT Computational Geometry column, and I'll post it here when it's done.

Many people had asked me when the talk slides would be available, and I'm happy to announce that all the talk slides are now up at the workshop site.

I strongly recommend looking over the slides if you have the time: these were excellent talks by great speakers that gave a masterful overview of their specific areas, as well as challenges for the future.

Some highlights from day 2 of CGWeek:


The Cheeger inequality is a well known inequality in spectral graph theory that connects the "combinatorial expansion" of a graph with "spectral expansion". Among other things, it's useful for clustering, because you can split a graph using Cheeger's inequality to find a "thin cut" and then repeat. There's been work recently on a "higher-order" Cheeger inequality, that allows you to cut a graph into $k$ pieces instead of two by connecting this to observations about the first $k$ eigenvectors of the Laplacian.

The above paper generalizes the notion of combinatorial expansion versus spectral expansion in a very different way. Think of a graph as the 1-skeleton of a simplicial complex (i.e the set of faces of dimension at most 1). Is there a way to define the Laplacian of the complex itself ? And is there then an equivalent of Cheeger's inequality ?

It turns out that this can indeed be done. Recent work by Gromov and others have shown how to define the notion of "edge expansion" for a simplicial complex. Roughly speaking, you compute the edge expansion of a cochain (a function of a chain) by endowing it with a norm and then looking at the norm of the edge operator with respect to the norm (sort of) of the cochain itself. What is interesting is that if you choose the underlying coefficient field as $\mathbb{R}$ and the norm as $\ell_2,ドル you get the spectral equivalent, and if you choose instead $\mathbb{Z}_2$ and the Hamming distance, you get the combinatorial equivalent.

It's known that for 1-skeletons, and even for things like persistence, the underlying field used to define homology doesn't really matter. However, for this problem, it matters a lot. The authors show that there is no equivalent Cheeger's inequality for simplicial complexes ! They also look at random complexes and analyze their properties (just like we can do for random graphs).


Suppose you have three Gaussians in the plane, and you look at the resulting normalized distribution. You expect to see three bumps (modes), and if the Gaussians merge together, you'd expect to see the modes come together in a supermode.

Can you ever get more than three modes ?

This is the question the above paper asks. It was conjectured that this cannot happen, and in fact in 2003 it was shown that it was possible to get 4 modes from three Gaussians (you can get a little bump in the middle as the three Gaussians pull apart). In this paper, they show that in fact you can get a super-linear number of "bumps" or critical points for $n$ Gaussians, and these modes are not transient - they "persist" in a certain sense.

This is quite surprising in and of itself. But it's also important. A plausible approach to clustering a mixture of Gaussians might look for density modes and assign cluster centers there. What this paper says is that you can't really do that, because of the "ghost" centers that can appear.

Other quick hits:

• Chris Bishop ran a very interesting workshop on Analysis and Geometry. While I couldn't attend all the talks, the first one was by Ranaan Schul gave an overview of the analytic TSP, in which you're given a continuous set of points in the plane, and want to know if there's a finite length curve that passes through all the points. The techniques used here relate to multiscale analysis of data and things like local PCA.
• One of the cool innovations in CGWeek was the fast-forward session: each afternoon before the workshops started, speakers were allowed to give a 1-slide overview of what would happen in their events. The slides were all placed in a single presentation ahead of time, and it was clocked so that people couldn't run on. It was great - I didn't have to do careful planning, and got a much better idea of what was coming up. We should do this for all talks at the conference !

CGWeek day 1 has my head spinning. Attending a mix of conference talks and workshops is something I'm used to in the DB/data mining world, but not in theory conferences. It's refreshing, exhilarating, and exhausting, all at the same time.

There were a number of great talks today at the conference and the workshops -- too many to do justice to. Here are some random thoughts:

• This year, there's a best student presentation award. My student Amirali Abdullah is one of the competitors, so I don't want to say too much about it, but I'll say that everyone uppped their game - the presentations by students were great ! Maybe they should have best presentation awards in general to improve everyone's presentation skills !
• Amir's talk went pretty well (if I say so myself). It was his first conference talk, but I thought it was well above the average (maybe this says something about the average :)). The talk was about approximate Bregman near neighbors.
• Very intriguing paper by Adamaszek and Stacho on the connection between homology structure of flag complexes and matchings that induce maximal independent sets.
• The workshop on geometric learning was fantastic. Lots to think about on multiscale representations, and distances to measures.
• Jeff Erickson has a four part liveplussing (one, II, trois, fear) of the business meeting
• Most importantly: Rio in 2013 !! Kyoto in 2014 (boo) !! OSU no way (I kid, I kid).
• Even more importantly: Herbert proposes changing the name of the conference to "Symposium on Computational Geometry and Topology". Major concern - what about the sausage ? Audience votes confusedly after Herbert promises a Klein bottle of beer for everyone.

As Jeff mentioned, we're organizing a workshop at SoCG called "8F-Computational Geometry" that looks at the past and future of the impact computational geometry has had "in the field". It was quite difficult to narrow things down to 8 speakers, and even harder to list only four areas where CG has already had impact.

The abstracts for the talks are now up at the workshop page. We hope to see you there !