Tuesday, March 24, 2009


Noam Nisan, the Complexity theorist turned E-conomist, started a new blog Algorithmic Game Theory. Since, as Noam says, the Computational Complexity blog occasionally writes about algorithmic game theory, I hope the AGT blog can also occasionally talk about complexity.

Which brings me to talking about communities. We as academics belong to many different communities. First based on employment, I have my research group, the EECS department, the Engineering school and all of Northwestern university (not to mention my courtesy/adjunct positions). But also based on research, first among my research colleagues and then computational complexity, theoretical computer science, computer science and the greater scientific and general academic world we live in.

All of these communities share the same basic mission: To develop, inform and educate on cutting-edge research. But when we have limited resources (funding, jobs, students, slots at conferences, people's attention), the priorities of different communities can come into conflict. At every level, we have to fight for our fair slice of the pie while at the same time working together to make the pie bigger.

This is the Computational Complexity weblog and I don't hide my research biases. But this I am also a theoretical computer scientist, a computer scientist, a scientist and an academic. Balancing these communities is a challenge for all of us.

I worry most about the CS and TCS communities. Already when I started graduate studies, computer science already became mostly a collection of separate nearly disjoint research organizations lacking for example a major general CS conference. Since then I have seen theoretical computer science go along the same path. No longer does it seem we keep close track of what is happening or even who the major researchers are outside our own specialized areas. 

Remember the roles we must play in the broader academic communities, the ones that go beyond the research that we follow and pursue. For as the famous Ben Franklin quote goes "We must all hang together, or assuredly we shall all hang separately."


  1. Is this your campaign speech?

  2. I agree and disagree.
    I AGREE that theory has become
    separate communities
    (Note my post on Huet winning
    some award and that LICS and CCC have little overlap.)
    But theory HAS been doing a good OUTREACH to NON-THEORY.

    Crypto and Security

    Algorithms + Bio= Biocomp

    Graph theory and Networks

    This is all to the good.

  3. Bill: outreach is all well and good, but it's not the same as having a coherent community.

    On the other hand: Lance, what do you see as some of the problems arising from the increased specialization you mentioned?

    Mathematics communities may provide a useful comparison. Math is similar to CS, in the sense that there are many communities (combinatorics, algebraic topology, geometric group theory, finite group theory, low-dimensional topology, ...). The different topics are all related, to greater or lesser degrees, but the communities are almost entirely disjoint in terms of people, journals, conferences, etc.

    Does mathematics suffer from the problems you see as arising from the fractured nature of CS? (I think not, but I'm not sure.) If not, what is the difference?