Skip to content

Ten Years of Blog Complexity

August 22, 2012

We mean: Happy 10-Year Anniversary of the Complexity Blog


Lance Fortnow is famous for many things, but one is his blog Computational Complexity, which he created exactly ten years ago today. It endured a brief hiatus in early 2007, but has come back stronger than ever with the partnership of Bill Gasarch. It has averaged almost 200 posts per year.

Ken and I wish to congratulate Lance—and Bill—on this great accomplishment.

The theory community would not have been the same this last decade were it not for their hard work. Their posts also have some computer-science attributes. One has been their efficiency. Another is maintaining “invariants” like we do—in their case, most notably the famous light-green background:

So we would like to thank Lance. Well besides doing so online, I can now just walk down the hall to the Chair’s Office, while Ken can go through a specially-tight kind of social network. Ken calls this the “-Mate Graph“: roommate, officemate, housemate, mate-mate…, with links defined by shared living or work space. Ken’s wife’s college roommate’s husband shared an office with Lance while they were graduate students at MIT. We both look forward to many more years of keeping Lance “in the family” and online.

Early Posts, and a Comment on Comments

Lance has noted the brief first post he made ten years ago today, while his post the following day had the first complexity content. It noted a “breakthrough result,” record attendance at the Complexity 2002 conference, and Madhu Sudan’s Nevanlinna Prize. Then it asked a question about randomness which we reproduce below. The next post gave a nice evocation on changes in how results are communicated, along lines we recently covered.

Then came a pre-announcement of an invariant feature, the “Complexity Class of the Week.” Nice to relate, the first one, the class {\mathsf{S_2^p}}, connects Buffalo to Georgia Tech. Namely, Alan Selman’s student Samik Sengupta showed that if {\mathsf{NP}} has polynomial-sized circuits then the polynomial hierarchy collapses to {\mathsf{S_2^p}}. This class sits inside the original upper bound {\Sigma_2^p \cap \Pi_2^p} from my theorem with Dick Karp, and inside improved upper bounds such as {\mathsf{ZPP^{NP}}} that came later.

This post also was the first one to draw a comment—but the comment itself came in October 2010 and was undoubtedly intended for a different post. It took a long time for real-time comments—by members of the community and onlookers alike—to become a feature of the blog.

Now many of Lance and Bill’s posts, especially on topical issues, have gathered many dozens of comments. This is an important function, as it enables timely conversations of the kind that Ken and I would experience on such a scale only at conferences, often months after the fact. Comments do mean a lot of below-the-surface work for the bloggers, not so much in syntactically “moderating” them but in semantically moderating the discussions when needed or as appropriate. We are thankful that the theory community has for the most part been substantive, well-behaved, and constructive.

Open Problems

Lance’s second post passed on a query from Joe Kilian, and since comments weren’t in effect then, maybe it is timely now:

Primality, until now, has always been the key example of a problem that we knew how to solve quickly with a probabilistic algorithm but not without using randomness. If the new primality algorithm had been discovered in the 70’s would randomized complexity still have developed as well as it did?

Again, we wish the Computational Complexity weblog many more years.

Update: Lance tells me (Ken) that Blogger did not have a comments option when he started. He used a third-party method, but those comments are now lost.

3 Comments leave one →
  1. Istvan permalink
    August 22, 2012 11:22 pm

    The intersection of FPRAS and sharp-P is not empty, so still there is a place for random algorithms/randomized complexity. So unless FP = sharp-P, random algorithms remain important.

    • Istvan permalink
      August 23, 2012 12:03 am

      Whoops, I ment that the intersection of FPRAS and sharp-P-complete is not empty… So unless FP = sharp-P random algorithms remain important, since some of the ‘hard’ counting problems are easy to approximate.

  2. August 23, 2012 12:30 am

    I can add as an “open problem” a request for interesting paths in the “-Mate Graph.” I can get to Bill Gates if I stretch the office part a little: my sister-in-law worked for one of Martha Stewart’s aides for awhile, and Stewart dated Charles Simonyi high up at Microsoft for 15 years. Serious dating counts, and a direct “boss-of” or “co-worker-on-project” relationship should count, but not just working in the same company. Also being in a wedding party or an official signer/signee of a contract, but not just any friendship or business contact. Shared primary enterprise is another way of stating the link. And for best value the nature of the link should change at each step—so e.g. you can’t get global connectivity in a company just by transitive closure.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s