Thursday, March 10, 2011

STOC 1989

A student at Northwestern gave a presentation about a STOC 1989 paper. I've been to well over a hundred conferences and the memories of many just merge into each other. But some conferences stand out in one's life and STOC 1989 was definitely one of those for me.

I was just finishing my Ph.D. at MIT and took my first trip to Seattle for this conference. The Boston Red Sox were staying at the conference hotel and we saw them lose to the Mariners in the Kingdome, a stadium I do not miss. I gave a talk on a paper that we later had to retract.

But above all I remember going to this mid-May conference with no job offers for the next year. I had planned to spend the reception asking people about job opportunities but my heart wasn't in it and I started drinking instead. Janos Simon came up to me and told me that Chicago would be making me an offer. It took all I had to give a coherent response and not toss my cookies on him.

The student was a baby at the time.


  1. This is a great, great post. Thanks!

  2. is the "exists an A s.t. BPP^A = BPTIME[n]^A" question still open?

  3. Very nice post. Awesome way to increase your STOC count ;)

  4. i wished i had a name11:21 AM, March 10, 2011

    nice nice. can you tell us which current paper instigated this post ?

  5. Completely tangential to your point, but
    I can't help but be fascinated by the mechanics of retractions in a world of paywalls. If somebody paid for access to the original article, would they get access to the retraction for free? Is it a "pull" (you have to ask for it) or a "push" (you get the 'paper recalled' notice unbidden)? Is it ethical for me to read the whole retraction even though there is a link that asks me to pay $15 to get access? Why would anyone ever pay for a 1-page paper when the free preview shows the entire page?

  6. Anon 1: To the best of my knowledge the question is still open though Rettinger and Verbeek (FCS 2001) made some partial progress.

    Anon 4: The student was presenting Feder's paper on network stability.

    Micki: I suspect ACM would make you pay twice. You can find them both on my web page.

  7. Lance and GASARCH, lately the left-hand column of your Computational Complexity website has been showing me exciting advertisements from degree-granting schools that promise me plenty of scholarships ... even in computer science and information science!

    These opportunities sure look great ...and so, I've clicked-on the ads and answered a few easy on-line questions.

    Now my Gmail inbox is filling-up with scholarship offers, and my phone is ringing every five minutes with calls from educational professionals who are *eager* for me to enroll in their colleges ... for tuition fees are astonishingly low ... with loan packages that make it so tremendously *easy* to get started !

    As the surfers say, I'm STOC'd! ... and so I'd like to thank everyone associated to the Computational Complexity weblog—hosts and posters alike—for associating themselves to these fabulous educational enterprises!

    And I'd like to thank too, all the authors at STOC 2011 ... who in aggregate comprise about 3 × 10^-7 of the planetary population ... for implicitly associating their high-level creative work also to these same academic enterprises ... enterprises that appeal so much to the hundreds of millions of students, around the globe, who are desperately seeking meaningful careers and family-supporting jobs!

  8. John,

    Now tell us what you really think.

    You forgot the ads at the bottom of the page. My favorite is "College Grants for Moms" brought to you by "ads by Google".

    Mitigating circumstances:

    1. The good this blog does far outweighs the annoying. I am a newbie and I have learned alot in a relatively short time.

    2. The folks who read this blog are probably among those who are the least likely to be scammed by the dubious ads, especially with guys like you around voicing their opinions.

    Keep up the good work.

  9. Jim (Blair), I am in 100% agreement with all you say about the good this blog does ... my concerns were directed at the advertisements, *not* at this outstanding weblog.

    AFAICT, it was the American philosopher Laurens Perseus Hickok (1798-1888) who first said "Quantity has its quality" ... during recent months these ads have increased enormously in ubiquity and sophistication, not only on Computational Complexity, but throughout the blogosphere.

    Is this good? IMHO, no.

  10. M.I.T., Ph.D, I have it all; now I have no J.O.B........

  11. Anonymous says: "MIT, PhD, I have it all; now I have no JOB."

    Anonymous, there is a large literature on how this situation has come about and how it might be mitigated.

    What's tougher is to decide what portion of this literature vast literature is good. There's an article in Daedalus by Harvey Brooks titled "Technology, Evolution, and Purpose" (1980) that has held-up pretty well over the past 29 years (40 citations).

    Brooks' style is engaging, and his writings been much-praised by authors like Eugene Skolnikoff (whose writings also are worth reading).

    This article is a good start for anyone interested in considering these problems seriously and systematically.

  12. It seems to me that it would be useful to not just say "we are retracting", but also _why_ you retracted. Wouldn't it be useful to know what the problems were? I guess nowadays that could be handled with a blog post.

    It doesn't seem like CS gets a lot of retractions, at least not in my area (SE).