California Update Part 1

I spent Tuesday at the pre-EC tutorials and NetEcon workshop at Stanford. The highlight was watching Jon Feldman and Muthu Muthukrishnan give a tutorial on web advertising. While most of what they talked about was already within my range of knowledge, they presented it very well and it's interesting to see their view of a theoretical take on real-world advertising problems. (My experience with Google people, reinforced here, is unfortunately they only let out enough details to whet your interest, without giving enough details to be really useful. Not that I blame them. There are undoubtedly limits on what they can reveal, and obviously any individual can't know all the working details at a low level.)

Today I gave my version 0.1 talk on "Open Problems in Cuckoo Hashing" at Microsoft. I was blessed with a receptive audience, who asked questions and pointed out various typographical errors and other possible fixes. The highlight for me was when two of my TAs from last semester showed up for the talk. (One is doing a summer internship a few blocks away at Google, the other -- who will starting grad school in theory next year -- is the daughter of a Microsoft Researcher.) Since I'm sure they'll stumble across this, a big thank you for coming!

In the afternoon I saw an interesting talk by Rafael Pass on Game Theory with Costly Computation. The high-level idea is to include a notion of computation cost in the utility function, so that your utility can depend on how much computation you use, which might in turn affect your choice of game strategy. It seemed like an interesting conceptual idea, and the twist has some surprising implications (like Nash equilibria no longer always exist).