Guest Guest post from FOCS

[Noam: Since I didn’t go to FOCS, I asked Shahar to write a guest blog post from there.]

[Shahar: Noam asked me to write a guest post on FOCS. However, Shaddin wanted to write a post so badly that I had to let him guest post in my own guest post.]

Guest Post by Shahar Dobzinski
Guest Guest Post by Shaddin Dughmi

When Shahar asked me on monday night to write this guest guest post, my first reaction was that I wish I knew ahead of time so that I would take notes. Since much of this is from memory, I apologize for any unintentional omissions or inaccuracies. Since this is an AGT blog, I will focus mostly on AGT-related papers.

This year FOCS is being held in downtown Atlanta, and the conference hotel is only a few blocks from Georgia Tech. The conference talks are all in the hotel conference center as usual, though the celebration on day 0 was located at the Lecraw Auditorium at Georgia Tech.

Saturday featured the celebration of the 50th anniversary of FOCS and the 20th anniversary of the ACO program at GATech. There were talks by four distinguished speakers: Richard Karp, Mihalis Yannakakis, Noga Alon, and Manuel Blum. All four talks were inpsiring. Manuel Blum’s talk on “Can TCS get a grip on Consciousness” was particularly entertaining and thought provoking. In the talk, Manuel chronicles his own personal journey towards understanding consciousness. The talk culminates with a description of “Global Workspace Theory” as a model of consciousness. Manuel draws concrete connections between this model and mathematical proofs, suggesting that TCS can benefit from models of consciousness as guides for high-level planning.

The conference talks were held in two adjacent conference rooms on the second floor of the conference hotel. Luckily, there was an adjacent conference being held on the same floor called “The Secrets of the Millionaire Mind”. The colorful characters from this conference occasionally ventured into the same lobbies as the FOCS audience, and doubtless managed to recruit many TCS graduate students who are fed up with meager stipends and left-over pizza.

There were two AGT sessions. Due to incurable jetlag, I unfortunately missed the first one on Monday morning. Luckily, however, all talks will be available online soon. Nevertheless, word around the conference lobby was that Amin Saberi’s talk on Convergence in local interaction games was fantastic. The second AGT session was monday afternoon, featuring three talks. The first talk was on Rationalizing Network Formation, where Kalyanaraman and Umans prove hardness results on inferring valuations of players in network formation games. I interpreted this as a hardness result for effective market research. The second talk in that session was on pricing strategies for Revenue Maximization. In this talk, the authors obtain improved lower and upper bounds on pricing strategies for revenue maximization when a limited number of items are sold to bidders with unknown subadditive valuations. The lower bounds apply to the previously studied static single-price, and they relax the model to one that allows prices to vary with time. An interesting question that was brought up after the talk was whether their results could be improved
by using a benchmark other than welfare. The third talk was on my paper with Shahar Dobzinski (the guest blogger one level up in the blogging tree), where we introduce a new class of truthful-in-expectation mechanisms and use it to get a truthful-in-expectation FPTAS for multi-unit auctions. We also show the first separation between truthfulness-in-expectation and universal truthfulness.

All in all, this FOCS was the usual mix of talks, good conversation, and blossoming collaborations. The southern hospitality was warm, and the sourthern food was an experience. As revealed in the business meeting, the next FOCS will be held in Las Vegas! In light of this choice of location, lets hope they tape the talks next year as well for those of us one roll of dice away from the big one!

Advertisement