The concept of an approximation

We're always searching for new ways to communicate cool ideas in theoryCS to the outside world, and the list gets more and more esoteric each time one thinks about it. But in my interactions with people, people generally unfamiliar with algorithm, and theoretical computer science in general, I'm constantly amazed at how counter-intuitive the very notion of an approximation appears to be.

A typical conversation goes something like this:

Person: Oh this problem is NP-hard so we ran this heuristic
Me: Have you tried approximating it ?
P: What do you mean ? Our heuristic seems to be reasonable.
M: I mean an algorithm that guarantees that it'll get close to optimal.
P: But how can you know that ? It's hard to find the optimal solution, global minimum, yadda yadda yadda...
M: We can often prove an answer is close to OPT without knowing OPT itself.
P: [total silence]

This kind of thing happens often in research conversations, as well as in the classroom (where it's less surprising I guess). In fact, one person was so amazed at the idea that even proving an approximation could be NP-hard that we spent a good semester plowing through the PCP theorem (at least parts of it).

I'm not dissing heuristics: it's often the case that either the approximation guarantees one can show are too weak, or that the claimed bounds don't match the empirical performance. But I do think it's important to at least ask the question of whether provable approximations exist, much in the way people in CS are now reasonable comfortable checking (or asking the resident theoretician !) if a problem is NP-hard.

But you can't ask till you know. This is one of the main reasons I teach a smattering of approximations in my graduate algorithms class (and why I teach some randomization as well). The concept of an approximation (especially when you can't find the actual answer) is a surprisingly slippery conceptual leap, and requires mental agility that goes beyond the standard "algorithms toolkit" that focuses on issues of performance.

The Katayanagi Prize

Via the Baconmeister (er.. the Quantum Pontiff), we hear that Christos Papadimitriou and Erik Demaine have received the Katayanagi Prize. Christos gets it for "research excellence":

The Katyanagi Prize for Research Excellence will be awarded annually to an established researcher with a record of outstanding, and sustained achievement.

and Erik gets it for "emerging research leadership":

The Katyanagi Emerging Leadership Prize will be awarded annually to an individual recognized as an emerging research leader.

Congratulations to both of them, (and do read the Dr. Dobbs interview with Christos, where he shows that he knows what "Guitar Hero" is :))

Edge people...

Bill Gasarch has an interesting post up comparing attendance numbers at SoCG and CCC. He introduces the interesting notion of 'edge people': people in related areas who wouldn't normally attend the conference, but would because of locality.

This of course makes me a little worried about 2010. We have a rather large 'edge' community at the U. of Utah itself within SCI. But Utah as such is fairly geographically isolated (and indeed, there's a general belief that our department suffers a little in perception as a consequence), so we don't get the 'edge' crowd that places like NYC and Maryland potentially get.

I say 'potentially': as always, it's probably possible to get data on this. Specifically, if one had access to historical attendance lists (not numbers) for SoCG, one could first identify candidate 'edge' people (either by subjective eyeballing, or even more numerically as people who only show up "rarely" and publish "rarely"), and then figure if there's a correlation between location and presence of an edge crowd.

Similarly, one might even do this for CCC vs SoCG although as one commenter points out, the larger number of total unique authors on SoCG papers might be sufficient to explain the discrepancy in attendance (Paul Beame's argument about competing conferences is also valid: I couldn't imagine going to FOCS, STOC, SODA and SoCG every single year, in addition to the various DB/data mining conferences I attend).

Women in Computing workshop, and a new blogger

Sorelle Friedler, UMD grad student in geometry, tireless staff volunteer at SoCG 2008, and former AT&T summer visitor, has a new blog. One of the first things she writes about is the Women in Theory workshop at Princeton that ran Jun 14-18. Add the feed, folks !

Money Money Money

(ed: three NSF posts in a row ? maybe you're a little obsessed with funding ?

As CRA and USACM are now reporting, the president just signed a bill that among other things allocates 62.7M in supplemental funding for the NSF. However,...

Funding for the National Science Foundation is split 70/30 between education and research programs at the Foundation with $40 million going toward the Robert Noyce Teacher Scholarship Program, which “seeks to encourage talented science, technology, engineering, and mathematics majors and professionals to become K-12 mathematics and science teachers

Which means that only 22.7M is left to be divvied up among the many directorates. Optimistically, that's roughly 44 new proposals, over ALL of NSF. Hmmm....