Approximation Algorithms Workshop, Princeton 2011

This past week, I’ve been kept busy by attending a workshop on approximation algorithms, hosted by the Computational Intractibility at Princeton University. The particular workshop is this one , the purpose being to recap the last decade of advances in this field and to set the direction for the future. It was a five-day workshop with something like thirty speakers in total, with talks ranging from 35 minutes to an hour. It was my first major workshop that I have ever attended! It happened somewhat coincidentally, as I had emailed someone from the department for something totally irrelevant and got a reply regarding it from my professor for the approximation algorithms class I took last semester - he encouraged me to attend the workshop this week if I was available and so I did. There were maybe three or four undergraduate students apart from me at the conference and it was pretty amusing to have every conversation start with “So which year of the PhD program are you at?”

There were some really quite amazing talks, such as one by Vijay Vazirani who did a overview of how much progress has been made on the twenty-one problems he predicted last decade would be the major ones in the field (at least 16 of them have either been conclusively solved or made substantial progress upon). It was a pretty exciting lecture and what was really cool was that the name “Vazirani” had come up again and again when we were studying approx. algorithms in class and it was pretty amazing to see him in person. He was also one of the three authors of the famous KVV Theorem (Karp-Vazirani-Vazirani) that gave an optimal result for any approximation algorithm for online bipartite matching. That theorem came up over and over again in other talks too.

Another cool talk was by Subhash Khot, inventor of the Unique Games Conjecture in his seminal paper, On the power of unique 2-prover 1-round Games. He reported on progress on the relations of UGC to other problems. Indeed this conjecture as well made its way into a good number of other talks. I had only very vaguely heard about UGC before this, but after hearing so much about how powerful it is, it’s pretty amazing. It ties in to a bunch of other theorems (If UGC is true, then …) and all of the results we’ve seen so far (that I’m aware of) derive reasonable conclusions with the assumption of UGC. It’s more evidence that it’s probably true and if it were ever proven to be so, it would represent a major step forward in this field (and as one speaker said, if it were false, we’d basically be back at square one).

My professor gave a talk on finding dense subgraphs inside graphs. He converted the problem into a decision problem of whether or not we can distinguish whether or not a graph has a dense $k$-subgraph (basically a set of $k$ vertices with a lot of edges between them). It was mostly understandable because I have a tiny bit of background in graph theory, but nonetheless a very difficult problem indeed. The talk was really interesting and it was a shame it was so short.

There were other talks by people from Google Research, Microsoft Research Labs, Bell Labs, and several universities around the world. I really wish I could explain every single talk that was given over the five days, but unfortunately my memory does not serve so well. The take-home message for me was that this is a truly exciting field and one that is filled with many, many brilliant people (duh) and that is being so very actively developed upon. It was an overall awesome experience to be in the company of such great researchers. I just wish I knew more than I did so I could gain more from attending. But that’s what the future is for!