Tuesday, October 28, 2008


Here are some notes from FOCS 08.

Gagan Aggarwal and I gave a tutorial on the theory of sponsored search auctions. Gagan went first and did a fantastic job with the theory of single auctions. Usually people just describe the generalized second price mechanism. Instead, Gagan chose to start off with the Meyerson's pricing scheme and derived various mechanisms naturally. Her talk showed the triumph of Ecom+CS theory: a lot of understanding of single auctions. I went later and spoke about running many auctions (not repeated ones) and the role of budgets. Here, nice theory is far off. We mostly have partial and demi-partial results. I described some of these: 1,2,3,4. Time worked against me, and I skipped parts, in particular, discussing the case of multiple, related slots, beyond this. A feedback I particularly liked (paraphrasing), "I did not know there was so much to do in sponsored search auction theory."

About the conference: Nikhil has nice results with R. Kannan on computing market equilibria using some algebraic geometry (he asked, "Are prices irrational?" :) and showed that they were roots of polynomials with signs, and yes they were.) Mihai P. loomed large, and I felt an odd excitement about data structures during his talk on dynamic connectivity (graph connectivity when nodes are inserted/deleted with connections to geometric connectivity) and (data) structures (where he showed this picture of lower bounds). Milan Ruzic spoke about his results with Piotr Indyk on sparse recovery problems: his paper showed why work on this problem has become a battle of tables (mea definitely culpa)! Finally, Assaf appeared with transparencies and enacted a talk, like in the past, I gathered. Many talks ended with the last slide asking "What happens in the general case?". The audience in most cases did not ask questions, perhaps mentally resolving to go read the proceedings.

It was great to see Sudipto Guha in a position of great responsibility, feeling it and living up to it. Sincere thanks to all the organizers and the volunteers. The conf hotel is one of many escalators, Escher-esuqe stairs and few signs, but had great views from 33rd floor, the scene of the reception and the tutorials.


Anonymous Anonymous said...

Are the slides of the tutorials available?

11:45 AM  

Post a Comment

<< Home