Wednesday, October 27, 2010

FOCS 2010

I am back from FOCS 2010, where I gave two talks:
  • a tutorial on data structure lower bounds: PPSX, PDF
  • a regular conference talk on distance oracles: PPSX, PDF (for this paper coauthored with Liam Roditty).
This paper caused some amount of fun in certain "inner circles", which I think I should share with a wider audience. If you read the paper, the algorithms repeatedly grow balls (aka shortest path trees) around vertices of the graph. After obsessing about growing these balls for more than a year, I found it natural to name the paper "How to Grow Your Balls". At least it allowed me to begin various talks by telling the audience that, "This is a topic of great economic importance; I receive email about it almost every day."

The committee took its role as Cerberus at the gates of Theory very seriously, and refused to accept the paper under the original title. In the process, many jokes were made, at least some of which transpired outside the PC room. I won't post them here, as the PC probably intends to keep some decorum. (But if you get a chance, ask your friend on the PC about that proposed proceedings cover.)

So the title changed, but I stretched the joke a bit further by titling the tutorial "How to Grow Your Lower Bounds".

This episode confirmed two things that I already knew. First, this community insists on taking itself way too seriously. For comparison, the title certainly triggered some PR alarms inside AT&T. But it made it through, perhaps because I told people that it's in the interest of AT&T Labs to prove publicly that it's a real research lab: it lets researchers be researchers, which includes being silly at times. Given the reputation of PR departments in American telecoms, it's a bit sad to find that the theory community has a higher bar on form.

Secondly, I should turn it down a notch with this blog. Several people said they had expected me to withdraw the paper rather than change the title. I found it quite amazing that people had such an image of me. Perhaps it is time to emphasize that I'm doing my research because I think it's important and cool. The horsing around is, well, not quite the main message.


pálenica said...

As someone who has spent a good chunk of his time in grad school thinking about ball-growing algorithms (in the context of approximation algorithms for network design problems) I fully sympathize.

That being said, there were plenty of people before either of us who wrote papers on ball growing and none had the balls to use a title like yours.

Anonymous said...

The tutorial on how to grow your lower bounds was given in ballrooms 1 and 2. Amusing.

Anonymous said...

You may want to check out the titles in the educational content mentioned in this Toronto Star article:'shealth/article/877934

Anonymous said...

Haha, this post is so hilarious!

Anonymous said...

Amusing video: "So you want to get a PhD in theoretical computer science?"

GASARCH said...

Check it out


Gil Kalai said...

Dear Mihai

I think it was a good call to avoid this direction of humor in the title/lecture. (Overall, without taking it terribly seriously, and with a lot of toleration to people's silly things I support politically correctness.)

Anonymous said...

Perhaps you know aobut this:

Mihai said...

This was a popular puzzle among math students when I was back in Romania. Glad to see it got completely solved :)

Anonymous said...

@ Mihai, Dec 12 anonymous

That weizmann institute paper is pretty hilarious, but not least of all, because their solution for a "complete graph orgy", aka, a gay orgy where everyone has sex with everyone else, seems to necessarily involve some people using the same surface to give anal sex as to receive anal sex.

I think its safe to say, this solution is "highly academic". So determining the minimum condom number for a safe, sanitary gay orgy may still be open.