The Future of Computer Science : Foundations

A Proposal by Michael Mitzenmacher


Looking at the state of computer science, and particularly the state of theoretical computer science, many of us are concerned that up-and-coming students don't realize how exciting our field is. Other sciences may seem much bigger, more relevant, and more interesting: the impression is that physicists study the Big Bang and the origins of the universe, biologists study our DNA and find cures for life-threatening diseases, while computer scientists write code and go work for large companies.

As computer scientists, we wonder what we can do to let students know the great problems we have to solve, and their scientific and practical importance. It would be thrilling to have a prophet -- a Feynman, a Sagan, a Gould, or another Hofstadter -- to write something that would galvanize the general population, and especially the young, to get people excited about the future of computer science again. Perhaps one of us could do it alone, but it seems like a big task to me.

I think of this as a grand challenge for the theoretical computer science community. So I am proposing a community-written book, that will be available on the Web. Each person who wants to take part gets a chapter, explaining something exciting about computer science, and where it is going over the next decade (and beyond).

My initial intention is that the book be theorerically focused. However, I do have a very broad notion of theory, and a very broad notion of what this book should be, so please don't hesitate to let me know if you have a good idea for a chapter.


We need some simple rules to keep people on track, with some notion of consistency. However, I don't expect the book to be a single unified whole. It is perfectly fine if notation and examples are repeated in various chapters. Arguably, that would be a virtue. So here are the proposed basic rules:
  1. The intended audience you should have in mind when writing a chapter is smart high school sophomores. I see this as the most important rule. The goal is a book (or, more concretely, a collection of chapters) the general populace can pick up and read, to learn about computer science and why it is interesting. We want to hear people say: I decided to try computer science because of this book.

    This rule has some corollaries. First, fewer equations, more pictures. Second, lots of examples. Third, simple language. I do not mean to suggest that we talk down to the audience, or assume that they are mathematically ignorant, but that we assume as little as possible, and try to reach the broadest audience.

  2. Each chapter should explain something already known and understood, and why it is significant.
  3. Each chapter should explain a specific, but big, open problem that one hopes might be solved in the next 10-20 years, but probably not before that.
  4. Each chapter should be roughly 15 book pages. If we can have 20 chapters, that will be about 300 pages, which is plenty. That's a guideline; I expect some variance.
  5. Each chapter should include at least 3 easily available references for more information. These could include Web references -- links to pages people can look at.
  6. We would like to book to be a mix of all that is out there. Some chapters should be complexity-focused, some should be application-focused. Some should be pure CS, some should be how CS relates with other fields. Some should cover the absolute basics (what is NP? -- something like Chazelle's already-famous essay), some should stretch the reader. We want a good mix.


I will serve as manager and editor for the content. In my mind, that involves the following:
  1. I will maintain a web site for and publicize chapters.
  2. I will edit chapters (in cooperation with the authors) when they are submitted to me. As manager and editor, I reserve the right to not accept content that is not suitable, according to the spirit or letter of the rules.
  3. I will handle copyright issues. All copyrights remain with the authors; however, an end goal of this project would be a hardcopy book, under a suitable publisher. Hence, it should be understood that submission of a chapter to me and posting of a chapter on this web site corresponds to a non-exclusive right of publication not only on the web site, but in any future book arising from a collection of these chapters.
  4. I will, when appropriate, try to find a publisher. In case of publication, all profits will be donated by all authors to SIGACT or similar appropriate organizations for the advancement of theory. (A primary goal would be to establish a fund for reducing student fees or providing student travel grants for conferences.)