FOCS and Sundries

Woody Allen (What's up, what's new: his early films) said, "80% of success is just showing up". I did. FOCS for a day was fun. Among other things, I heard Mihalis talk on his paper with Kousha Etessami, On the complexity of Nash equilibria and other fixed points. The talk, despite technical difficulties (was it Warren Schudy who was helping out?), started with a simple Nash equilibria question and pretty soon included some nice fixed point theorem stuff, sophisticated questions about real-valued computations and myraid complexity classes. Note to self: All relevant. Must read the paper.

Anecdote: MM cited RC as saying, "I have this algorithm that will solve all your problems". I asked, "Greedy?".

Doing napkin research: Yesterday, over lunch, I was trying to understand a matrix low-rank approximation problem a colleague posed, using the tools I had to do algebra, and Michael Riley asked me if it was a 2-napkins problem. We discussed if there should be designer napkins for doing math over meals.