Friday, October 30, 2009


Last month I suggested that students should go to FOCS even if they didn't have a paper there. I doubt my post had much to do with it, but I heard FOCS did attract many students this year. However there seemed to be fewer of the older participants and in particular very little news from the blogosphere.

Some news beyond my student reports earlier this week: Lipton posted about the 50th FOCS day of talks. Shaddin Dughmi guest posts for Noam. Joe Fitzsimmons "pretends" to be a computer scientist and tweeted from FOCS. Shiva Kintali promises a post soon on open problems from FOCS talks.

Still sad to see the 50th FOCS with such limited coverage. So if you went, let me know how you enjoyed the conference. What were your favorite talks? Any controversies in the business meeting? What's the gossip? Inquiring minds want to know.


  1. omg wat's happening to focs ?

  2. The middle 2 talks were technical, focused, and predictable. The remaining 2 talks held the promise of taking off, but the contrast between them was striking.

    The last talk took a very difficult topic with very little known in it and made it come out alive and inspiring. The first talk transformed a topic with numerous beautiful, profound ideas into a list of topics for a graduate course, with very little insight.

    Of course a list, specially with the disclaimer "personal" thrown in, is easy to whip up in a few of hours, whereas a talk that exposes deep ideas with clarity can take weeks, even if you know what you are up to (a big IF).

  3. Does anyone know if the videos for the FOCS webcast are up? They said they would do it this week...

  4. There were plenty of senior people at FOCS and not particularly more students than usual. There was just a shortage of senior bloggers.

    Mihalis Yannakis' 50th FOCS anniversary talk gave a beautiful exposition of the emerging classification of large classes of equilibria problems (many from algorithmic game theory) as either in FP, PPAD-complete, or FIXP-complete (a large class that includes the longstanding sum-of-squares problem as a special case). A number of papers in the conference contributed nicely to this classification.

    Smoothed analysis, too, had a number of prominent talks including applications to learning theory, which itself had a number of interesting and well-delivered talks. Among these was Alexander Sherstov's Machtey Award talk on the degree of the representation of intersections of halfspaces as polynomial thresholds.

    For entertainment there was Adam Kalai's miracle cure at the business meeting.

    Also amusing was Liber Barto's apology, in his talk on significant progress on the dichotomy conjecture for CSPs, that his talk would have "no O( ), no epsilon, and no proofs".

    In terms of nice things to file away for future use there was the item from Zeev Dvir's talk that there is a simple improvement of the Schwartz-Zippel Lemma: namely, one can upper bound the total multiplicity of zeros of a multivariate polynomial over a domain S by the same quantity usually used to bound their number.

    As has been alluded to before, all talks were recorded (and even streamed live, I hear, though I have not verified it).

  5. More pretending on my part:

  6. Unrelatedly, I'd encourage anyone reading the comments hear to check out Math Overflow. It's a math questions site for mathematicians (no calculus questions). I'm sure a lot of the topics TCS people are interested in would be welcome as well:

  7. ? can you please not waste the space advertising for such a thing ?

    and if you do, then have the courage to at least identify yourself. by the way i know who you are.

  8. Another call to get those videos online. Let's YouTube that stuff. Are we computer scientists or what?

  9. They are up now.

  10. I was there, and did get the impression that the conference was less attended by senior faculty than FOCS/STOC conferences in the past. I am not sure how to capture this with my imperfect recollection. I could have easily missed people (apologies if I did), but I saw 2 professors there from MIT, Costis and Piotr, (and only saw Piotr one day), 1 professor there from Berkeley, Dick Karp (at the day before, but not at the actual conference), and 0 from Princeton (however both Russell, Avi, and Valentine were there from IAS). Of course there were many others who were there too, but some of the regulars were absent.

    I also got the sense that there were less complexity papers than usual. I am not sure if this was the result of my warped perceptions, the fact that complexity researchers did not have many results this time around that warranted a FOCS paper, or the PC (I didn’t hear any complaints from complexity theorists getting good papers rejected, so I will assume it is one of the previous two reasons.) But this may have contributed to people like Lance, Omer, Cynthia, Luca, Salil, and Madhu not attending (though perhaps they had other reasons, I don’t know).

    Thanks to all those people who contributed to organizing the conference, and to all those who did come which made the conference enjoyable for me. For all those who did not attend, I hope to see you at STOC.

  11. I agree with some other comments: less senior people than usual.

    Lack of comments on the blog was perhaps disappointing, but Richard Lipton's text about the FOCS Theory Day was a real gem.

    Business meeting:

    FOCS'2010 in Las Vegas, Hotel Monte Carlo (less than 100$ per night), similar dates as this year, PC chair: Luca Trevisan.

    TCS chapter in IEEE is discussing the idea of a new IEEE journal.

    FOCS proceedings should be available online from IEEExplore and some other (?) venue. Paul Beame claimed that most of the universities should access to it.

    Books proceedings didn't have two papers.

    Two talks has been canceled (with the same speaker who missed his flight and who couldn't then stay until the last session, where it would be possible to have free slots).

    There was interesting discussion about publishing conference version papers in journals (caused by the 20 pages papers in SODA, which will make problematic to publish some of these papers in journals). OR and economics journals (typically) won't accept such papers unless some major changes in the paper are done.

    I think, there were videos make from all talks; don't know when/where/how they will be available.