Back from FCRC

Just returned from FCRC 2011, which included, among other conferences, EC (with workshops and tutorials), STOC, and CCC, in all of which I attended some talks, in addition to the plenary talks.  So much was going on, and there were so many competing things to do, that it is hard to give any flavor of the large event (maybe Lance’s post succeeds in describing the hectic atmosphere), so let me just mention shortly three talks which left an impression on me.

1. Valiant’s Turing lecture talk was a valiant attempt to point out the computational facet of evolution and call for a computational study of evolution.  This is not a completely clear agenda, but I did think that Valiant made a step in the direction of defining and motivating it.  I believe that this type of high-risk high-yield not-fully-clear agendas are exactly what Turing awardees should be focusing on, and what Turing-award lectures should be used for.
2. STOC best-student paper went to Analyzing Network Coding Gossip Made Easy by Bernhard Haeupler.  His talk was a model of talks that give you a take-away: he explained the problem (k messages need to be broadcast  in an n-node network and this is done using the following simple algorithm: at each stage each processor chooses a random neighbor and sends it a message), the logic of network coding (in order to escape from loosing a logarithmic factor due to the coupon collector, each message is not one of the original ones received by the processor in question, but rather a random linear (mod 2) combination of such) and a 1-slide understandable-on-the-spot proof that it works quickly (replacing and significantly generalizing previous  previous 30-page proofs).  Wow.
3. In EC, the paper Reserve Prices in Internet Advertising Auctions: A Field Experiment by Michael Ostrovsky (Stanford) and Michael Schwarz (Yahoo! Research) described an application of auction theory  in Yahoo.  They analyzed the distribution of advertiser values for advertising on about half a million keywords, and for each keyword calculated the optimal reserve price a’la Myerson’s optimal auction.  These new keyword-specific minimum prices replaced Yahoo’s previous fixed (10 cents, I think) minimum prices and indeed yielded a directed significant increase in Yahoo’s revenue for the quarter.  This is quite an impressive feat, although frankly I question Yahoo’s business decision of increasing revenue this way, transferring value away from advertiser, and in my opinion likely to drive advertisers away from Yahoo in the longer run.

Advertisement