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.

- 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.
- 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. - 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.

on June 15, 2011 at 7:23 am |ZeetHi,

Can you give a reference to the 30 page proof that Bernhard Haeupler simplified?

on June 15, 2011 at 8:09 am |AnonymousI think that this refers to references [1-5] in the paper’s bibliography. [1] seems to devote about 10 pages for the case of a complete graph.

on June 18, 2011 at 10:37 pm |AnonymousThe full version of the ”Algebraic Gossip” paper for the complete graph can be found here: http://web.mit.edu/medard/www/papers/ITRevised.pdf

It is 49 pages long – not all of it is proofs of course.