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 :)

## Monday, November 5, 2007

### Napkins

Posted by Mihai at 4:20 PM

Subscribe to:
Post Comments (Atom)

## 4 comments:

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

Some of your ideas are not new:

http://en.wikipedia.org/wiki/Scottish_Book

Napkins are also less likely to give paper cuts :)

Alex

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

~C

Post a Comment