Wednesday, April 23, 2008

The TheoryCS Book

I'm glad to see interest of various kinds in the Book on Computer Science (I really need to come up with a catchy name) I talked about last post. And yes, as many of you correctly interpreted, I'm looking for volunteers!

To flesh the idea out for you, here is (with some small updating) the original proposal I sent out for what I had in mind. For those who don't like clicking, here are what I wrote as the main 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.
I've had many people tell me they think this type of writing is hard -- that is, writing for a general, non-research audience -- and I understand that. This task won't be for everyone. But if, as a field, we can't articulate to a general audience what we do and why it's interesting -- and in particular, if we can't provide some idea of where we hope we'll be in specific subareas a decade or so from now -- well, then I think we're in big trouble in the big landscape of science. I'm sure we can do it. I also think we haven't really tried hard enough to do it in the past, which explains things like our current NSF budget.

If you're wondering what such a chapter might look like, I have my chapter from back in 2006 available. (It's on coding, naturally.) I'll talk more about this chapter, and how much work a chapter is, next post.


Anonymous said...

I am just curious to know whether you have asked any high school kids to read your sample chapter and what's their feedback like. I really doubt how challenge it is to describe Comp Sci open problems to high school kids. Pesonally I believe it is infeasible at all---if they want to understand computer science well, they shall do a 4-year undergrad degree in comp sci. There should not be good short cuts...

Michael Mitzenmacher said...

Anonymous --
That's a great idea. If anyone knows any interested high school kids, please encourage them to look over the chapter, or just get in touch with me. We should get their feedback, throughout the process. I'm not at a stage where I know many high school kids. (I suppose I could ask some of the summer "geek" programs I used to be involved with to suggest some kids for me to contact, though.)

I have to say, though, that I don't agree with you that it's necessarily hard to explain comp sci open problems to bright high school kids. For example, here's a great open question: "Take two computers that are the same, except that one of them has the power to flip a coin whenever it wants, and the other doesn't. How much more powerful is the computer that can flip coins?" Now, that might not be as deep a presentation of derandomization as you might want, but I think it gets the point across in a way that would inspire the curiosity of a bright high school student -- which is really the point.

Anonymous said...


A very good idea. I have a couple of things. I was wondering about the process of getting the chapters written. Do you have (only) established researchers in mind? I think it's a good idea to also consider other interested parties like graduate students. The reason I say this is, being relatively freshly out of high schools, they would have a fair idea of "Oh, I wished someone had told me about these things back in school." Also, they may have a good grip over the level of presentation. This may mean more editorial work, but I feel it's worth a try.

What could be done is - you can setup a wiki for the book, and ask volunteers to put in chapter names and brief outlines. Also timelines. Among other things, you can do the filtering and delegations there.

And finally, I am not sure how much math content you are intending to put in, but I have wished there were some books that presented concisely the math building blocks of computer science. I am a PhD student from India, and somehow we are low on math during our undergrads, and need to pick up a lot in grad school. It would be great if that can be preempted.


Anonymous said...

Er.. I wrote my previous comment before reading comments to your previous post. I saw the discussion there about the utility of a wiki. Just to make it clear, I don't mean to suggest a wiki where people write chapters and others edit and so on. I only intend it to manage authors, delegations and suggestions.

Anonymous said...


I'd aim for about 2/3 that length, even given that you are imagining an open, illustrated format.

As David Molnar suggested, you should definitely call Dennis Shasha and ask him what he learned.

I wonder if the group can find a more salable term than "theoretical computer science." That's a mouthful and not the label you want for attracting high school students, unless you are just trying to get the math geeks to move over, and maybe not even then.


Michael Mitzenmacher said...

Harry -- I'll try calling Dennis sometime (and say that you sent me :) ).

I've been toying with a better title, which I think is necessary. I'm toying with

The Future of Computer Science : Foundations

which emphasizes that the book should aim to give insight into what the future holds, and is focused on foundations. But I'd love to hear better suggestions!

Anonymous said...

If I understand correctly, you'd like the chapters to be pretty much independent of each other, so that readers can skip around to what interests them. However, there is some foundational material that is liable to keep coming up over and over, and it might be a good idea to have some of that in its own chapter(s) near the beginning of the book. That way the authors of the more specialized chapters won't have to keep reintroducing the same material.

For example, you might want to have a chapter along the lines of, "What is an algorithm?" It could talk about informal notions of what an algorithm is, give some historical examples, explain why mathematicians and computer scientists need formal abstract models to help them prove results, and finally build up to TMs and the Church-Turing thesis. Such a chapter might not meet requirement #3 from your list (open questions), but it would lay the foundation for many subsequent chapters dealing with questions in computability and complexity theory.

The other general background area is discrete math. In your own chapter you make use of modular arithmetic and logical bit operations. Some other topics that are likely to reoccur are basic graph theory, propositional logic, and growth of functions. You might be able to organize this into a chapter, or maybe create an appendix for it. Either way, it will save the individual chapter authors from having to spend too much time explaining these items.

Michael Mitzenmacher said...

Kurt --

I completely agree with your comment. I would certainly be happy for someone to write an "introductory" chapter, covering many of the basic ideas (What is an algorithm? Why do we study complexity? etc.) that would not be "open" but would help frame the book. Like Chazelle's excellent essay, but with a bit more formalism.

I also think that a "math" chapter may be nice, but I would put that on hold, for several reasons. First, there's a risk that such a chapter could bore the intended audience. Math is generally better when introduced in context. I'd rather err on the side of having the same math introduced multiple times in multiple chapters (easy to skip; sometimes nice to see the same idea written up in multiple ways) than to have the book look like just another textbook. Second, I think the task of writing a "math chapter", if necessary, would best be done after seeing what math people actually use in the chapters -- after the chapters are done. (This could be done in going from the "online chapters" phase to the "book" phase.)