Monday, November 5, 2007


The inexhaustible Muthu came up with the fantastic idea of assembling napkins used for research-related work. This could turn out to be very interesting.

Here is my own contribution: a Starbucks napkin filled during a 2 hour caffeinated discussion with Alex. It contains the proof of a communication-complexity lower bound for near-neighbor search in L, matching the current upper bound of Piotr from FOCS'98. We were working on this problem during our summer internship at IBM Almaden (yes, yes, we're officemates but we had to go to California to write a paper together). As you might expect, the fact that we're now trying to finish the details has some correlation with the Nov 19 fireworks party :)


Anonymous said...

What I don't get is this: you went to starbucks to work, and didn't bring paper?! =)

Anonymous said...

Some of your ideas are not new:

Anonymous said...

Napkins are also less likely to give paper cuts :)


Anonymous said...

I think I spotted an error in line 5 of your proof. :p