Tuesday, April 22, 2008

Failure, and a Second Try

About two years ago, I went through a huge failure on a project. In the back of my mind, I always wanted to use this blog as a jumping off point for a second chance for this project. Now is the time. Perhaps some of you can help me fix this failure.

Back in early 2006, while I was on what's now known as the SIGACT Committee for the Advancement of Theoretical Computer Science, I was thinking about ways to promote theoretical computer science (TCS). One idea that struck me is that most people entering college from high school know nothing about TCS. If they've had exposure to computer science, it has been programming. Compared to the excitement of biology (we're figuring out the building blocks of life!) or physics (we're figuring out the building blocks of the universe!), computer science must seem to the average high school student to be, scientifcally speaking, a wasteland.

Now, we know this isn't true. Those of us in TCS wouldn't be in it unless we thought there were fantastic, mind-bending, potentially world-changing problems in the field. And I think history is on our side; computer science, and in particular TCS, has changed the world, fundamentally, and continues to do so. I don't think, though, we do a good job of promotion, showing the world, and in particular high school students who we might hope to attract to our field, the excitement of TCS. Somehow, our field still attracts talent, but it's an uphill battle. If we could change that, I thought, we could change the perception of our field, attracting top students earlier, and long-term creating a greater appreciation of TCS in computer science and across the sciences.

So in 2006, I dreamed up a project. I wanted a book that could be handed to high-school sophomores, to give them an idea of what TCS is all about. I wanted a book I could give to friends' kids -- heck, to my own kids, when they got to the right age (and wanted to really know what Dad did with his time). I wanted a book that would be interesting, engaging, and cover the wide swathe of work we do.

So, naturally, I knew I couldn't write this myself.

Instead, I wanted a group-book, with experts writing chapters in their areas of expertise. I reached out to about 40 or so people in the TCS community, asking them to write a chapter. I hoped first drafts could be done over summer 2006. And that by the end of the year, we might have a book ready for a publisher. About 1/2 the people agreed, and I sent occasional e-mails reminding and encouraging people.

And nothing happened. I think lots of people started, but never finished, their chapters. I heard a lot about how it was difficult to write chapters for the target audience, high school sophomores. It seemed for everyone that other projects, other papers, other things took priority. Disheartened, and busy myself, I let it go.

I still thought the project was a good idea. I still think so. So now, over the next couple of weeks, I'm going to revive the project here on the blog. I hope to change the nature of the project a bit, so my initial management failure won't necessarily repeat itself. It's something I've wanted to do since I started the blog, but I've kept putting it off.

I think it's time to try again. More to follow.


Anonymous said...

Looking forward to hearing more. I think this could be a very important project.

Anonymous said...

As I'm about to become a father, I've been gravely disappointed to discover an apparent lack of any children's book about CS. I've even thought about trying to write one myself, though I was thinking of something more basic and skewing younger than what you're proposing- something like an illustrated dictionary of terminology- algorithms, loops, stacks, queues, hashing, etc. Terms you'd get in an introductory course but without any programming.

I'd very much appreciate if you could get your book published within the next fourteen years.

Anonymous said...

This sounds like a great idea!

Shaddin said...

Perhaps physics didn't gain the majority of its popularity through books. It could be argued that TV programming such as the "cosmos" and all the "nova" documentaries did more to popularize physics and make it "cool" for the younger audience. Something like that for theoretical CS would arguably have a couple of advantages over a book:

1- Access to broader audience?

2- Easier to illustrate scientific concepts through TV. I'm sure the folks at Nova, PBS, and the discovery channel have a lot of experience in communicating technical concepts to a non-technical audience.

3- Less of a time commitment for the authors. All you would have to do is stand around looking pensive while the camera dramatically shoots in from a distance, and then give an over-dramatized explanation of a technical concept. Actually thats not true, i'm sure a lot of time goes into just designing the technical content of the show, but it still seems that it could be easier than writing a chapter since it would be more of a consulting role.

Michael Mitzenmacher said...

Anonymous 2:

Have a look at Computer Science Unplugged


which definitely skews younger, and is a fantastic resource. I admit, I haven't tried to get my kids into it yet -- but soon...

Anonymous said...

Here is a Slashdot review of a great children's book on network fundamentals:


and the book itself:


Anonymous said...

I think you should set up a wiki for this project and let people submit chapters or sections there. That way if someone gets bogged down with just partial results, others can jump in and add material or provide necessary editing, etc.

Michael Mitzenmacher said...

Kurt --

I understand a wiki would possibly be a viable way of doing this sort of project. But it's not the way I want to do it. I want to be able to ensure quality control and consistency by keeping control; I want writers to get appropriate credit, whatever that may be, for participating. Perhaps this will morph into a more wiki-style project as it goes, but that's not my plan.

Arvind Narayanan said...

I came here to suggest a wiki but Kurt beat me to it. Because of the novelty of the project, I think most people are likely to give up half way through a chapter (or push it down their priority list and never get back to it.)

Anonymous said...

Sounds like a promising idea, and I would even volunteer if that's what you're looking for.

Having a series of chapters that are completely disconnected (in both style and scope) might not be the best approach, though.

And I assume you would go beyond TCS, right?

Anonymous said...

I'm wondering how you were envisioning the end product to look - as something that could be used in high school classes as a text, or as more of a mass-market kind of thing?

Instead of getting a bunch of experts to write individual chapters, which could result in big swings in style and difficulty level, it might be better to just solicit from the experts what ought to be included from their respective areas. Then you could try to assemble that into a cohesive outline, and shop it around to publishers.

Once you get a commitment from a publisher, I don't think you'd have too much trouble finding someone to be the primary author if you didn't want that responsibility yourself. Writing for a high school audience, the person is not going to have to be an expert in each subject area.

(This topic comes up occasionally in the comments on Scott's blog, regarding promoting TCS to the general population more so than specifically to school-aged kids, but unless he's keeping it a secret we haven't been able to convince him yet to try his hand at this. If his SciAm experience hasn't disillusioned him too much there might still be hope.)

Michael Mitzenmacher said...

Kurt --

I don't imagine it as a textbook -- as far as I know, there's no call for a textbook in TCS at the high school level.

I'd see the end product as mass-market, albeit for a pretty small mass. I don't view it as a general audience book like I expect, say (plug) Harry Lewis' upcoming "Blown to Bits" to be. I expect it to be for a mathematically talented, scientifically interested high school student -- or people at that level interested in finding out about the field.

While having various writers leads to variation and consistency problems, I don't see that as a huge negative -- since the book will be exposing students to how large and varied the field is. In particular, since (as I'll explain in upcoming posts) part of the writing is to give some visions into the future, I think a variety of views is a positive.

On the other hand, given the lack of adequate books of this type, I think you're underestimating the problem of having one person (or even a small number of people) write such a book. And I think there's some value by having people with some expertise write individual chapters.

Michael Mitzenmacher said...

Arvind -- If the argument for a wiki is "So many people will want to get involved in this, and take part in so many different ways large and small, a wiki offers the best approach (a la wikipedia)," I can see the argument for it. Though it's still not the way I'd want to do it, personally.

If the argument is "Nobody really has the time, energy, or inclination to write a chapter for something like this, your only hope is somehow get 3 or 4 people to slap together something semi-coherent together by using a wiki-style approach," which seems to be what you're suggesting, then I would say a wiki isn't the right approach, and that the project will just fizzle out again. In which case I'll be disappointed in the result, but not the product.

Peter said...

You might want to try an initial go-round using blogs (not a wiki - wikis work best for facts, but creative writing seems to require authorship, which wikis are terrible at). The people who are really interested in popularizing the stuff often seem to have blogs of their own. Using this process you could quickly winnow out ideas that are not work pursuing and encourage the ones that are worth pursuing. Getting people to write a 3 paragraph summary of a chapter would enable you to quickly decide whether you would like it if they wrote a full chapter, on the basis of both the writer's style and the proposed content.

Anonymous said...

If one is purely trying to communicate content, then one example is the (New) Turing Omnibus by Dewdney which is quite good but misses the feeling of "what is it like to BE a TCS researcher" and does not have recent web-based applications of TCS. I think that a more popular TCS book may be more generally useful to the field.

Some of what makes a successful book that provides a basis for popular science writing is mythologizing of personality. In CS, maybe there are a Wozniak and Jobs in their garage, Gates and Allen at high school, but Alan Turing is our only mythical TCS figure, unfortunately a tragic one. We're really only in the third generation of TCS researchers but maybe it is time for some injection of personalities to liven things up. Physicists manage to characterize each other all the time in this manner without being embarrassed about it. (E.g. Everybody about Hawking, Brian Greene about Ed Witten.)

The market loves the "How X changed the world" books. Unfortunately, the one attempt of this kind that I have seen for TCS is the shoddy "Advent of Algorithm" by Berlinski. (Martin Davis tackles the origins but much less that relates more recently.) There is plenty of meat for this.

To my thinking the aspect that would be most accurate in the depicting how TCS operates would be something like James Burke's "Connections". Avi's talk at FCRC on the origins of the PCP theorem was way too technical relative to what one would want in such a book but pointed out the kind of unexpected connections on which our field is built. And, as Burke does, to keep things lively one may have to inject some personality.

EERac said...

Obviously I don't know the specifics of why things didn't work out the first time, but it seems like a great idea and I think a lot of people would get behind it (I certainly would). I'm not sure if the book needs to be specifically targeted at college sophomores, but a popular science TCS book is a long time coming.

With this type of group project, the most important task seems to be picking a good list of chapters/topics/examples. Given good outlines, you might even be able to rely on talented TCS grad student writers to get the ball rolling. Frankly, I'm not surprised experts in the community had trouble writing for a more general audience. Perhaps you could specifically seek out individuals who have written for popular publications such as Scientific American.

In terms of topics, have you looked at these to posts by Scott Aaronson?


They have some great suggestions for how to present fundamental TCS results. His essay on "who can name the biggest number" is also a great way to introduce to at least one aspect of TCS.


As long as I'm singing the praises of someone I haven't even met, I should probably mention Scott's class on quantum computing, as well as his recent job talk (which surprisingly is on iTunes U). Both do an excellent job of making complex TCS ideas accessible.

Also, speaking of iTunes U, perhaps a video lecture series could supplement the book?

Anonymous said...

Hi Michael,

When I was visiting Tsinghua University in Spring '06, Andy Yao was running a discrete math/intro to algorithms class for undergrads with a strong math background but more limited CS background. That semester, we also had a number of visitors, and Andy would ask the visitors to deliver a guest lecture targeted for this audience. Ashwin Nayak talked about the halting problem, Luca Trevisan on zero knowledge, Dana Ron on testing monotonicity, Oded Goldreich on pseudorandom functions, David Shmoys on 2-approximation for Euclidean TSP, and so on. The topics, the exposition, the speakers were fantastic. At some point, I raised the possibility of compiling notes from these lectures into a book (the hope being that it's a relatively small step starting from the lecture notes) ... unfortunately, that hasn't materialized as far as I know.

Indeed, there are already some excellent expositions on "theory gems". Two examples off the top of my head are Ronitt Rubinfeld's ICM survey on property testing, and Madhu Sudan's Princeton Companion to Mathematics article on error-correcting codes.

Srinath Srinivasa said...


This is something that I feel quite strongly about myself. One of the arguments that I use for students to get them interested in TCS is to claim that manipulating information is as fundamental as manipulating particles. Everything in this world can be claimed to be following the laws of physics -- except information! While the foundations of physics are obviously earthshaking, the foundations of computing and of information in general is just as much.

There is this book called "Great Ideas in Computer Science" by Alex Biermann published by MIT press, which does a fairly good job of providing that initial bit of excitement. But its audience isn't exactly high school students. I'm curious to learn more about this project.


Anonymous said...

You might find it useful to speak with Dennis Shasha at NYU if you haven't already. He writes the "Dr. Ecco" puzzle column for Dr. Dobb's Journal, and many of his puzzles have algorithmic motivations. (They've also been collected into some nice books.) While what you're proposing sounds like it wants a more explicitly expository character, it could still be helpful to talk to someone who's gone through the process of putting together a popular book. (Of course, maybe you've already talked with him.)

As for specific results to discuss, I've always found the concept of natural proofs fascinating. Getting there requires understanding pseudo-random functions, but the payoff seems worth it, in that it gives an explanation for why a large class of approaches to solving P ?= NP have failed (so far).

Rasmus Pagh said...

A personal experience: In high school I read David Harel's book "Algorithmics - the spirit of computing". It was the first thing that made me consider studying computer science rather than mathematics as a primary subject. I think this book, which is suitable for high school students, could be used for inspiration for a book with a wider view of TCS.

I hope the project will succeed!

Mark Wilson said...

Very active comments - I came to post a comment about David Harel's books, and have been beaten to it.

His book "Computers Ltd - What they really can't do" is a masterly piece of popular writing about computability and complexity. The earlier one about algorithms is excellent also.

I am volunteering what little skills I may have, as a mathematician who teaches algorithms courses, to your project. At the very least, I am good at proofreading!

Anonymous said...

Power to you! I believe this is the most significant blog post in the tcs blogoshpere in at least the past 5 years.

I always thought theorycs will eventually make its way, maybe in the next 40 years, into high school curricula and be taught along with biology, chemistry and physics (meaning not as an elective course available at select high schools but a basic and required part of the curriculum). Perhaps now it won't nearly take that long.

Soča said...

How close does Gary Flake's book The Computational Beauty of Nature come to your vision? Because from your description I'd say it's pretty close.

If so, it might be easier to talk to him and see if you can start with the material there and augment/modernise it.

Anonymous said...

I agree with the commenters who wonder if a book per se is the right way to go about this. Something interactive would surely have more appeal, and should also get get your target audience more immediately involved. Reading a book is awfully passive.

The television show idea is a good one; it would get immediate attention from a much broader audience than a book could reach. Coming up with a good story (or series of stories) with visuals won't be so easy but must be possible. Get the ACM's publicist to pitch this to PBS or Discovery or whatever, with the aim of getting broadcasts plus DVDs that can be sold to teachers and parents, in conjunction with a book or on its own.

I can tell you that the high school audience is a tough one to reach; what you really need to do is reach the teachers, which in this case means math teachers. If they read and like a book they will recommend it to their students, and I bet they're more likely to do both if there's some kind of TV tie-in.

There is a big infrastructure in mathematics teaching that you should try to tap into somehow. Some possibilities: get TCS problems into mathematics contests (see, eg, mathcounts.org), start a TCS summer school for high school math students, offer a course would-be math teachers, give talks to math clubs at high schools, propose/mentor research projects, write articles for The Mathematics Teacher... Presumably the ACM could lend some muscle in some of these areas; I notice the National Society of Professional Engineers is a sponsor of the MATHCounts contests. Also, your local mathematics faculty may already have programs that you could be involved in.

In the standard high school curriculum the major change now being proposed is to add some statistics. I doubt you'll be able to get TCS in ahead of that, but it ought to be possible to tie TCS better to the existing math curriculum.

Michael Mitzenmacher said...

Barak --

A glance suggests what I'm thinking of is very different. Perhaps I'm not describing it well.


Michael Mitzenmacher said...


Reading a book is awfully passive

I don't know. I guess I'm just dated. I found reading quite enjoyable as a kid (and an adult). I think it makes a lasting impression.

Many physicists I know picked up the Feynman lectures books when they were younger. Not the video. I personally hated the things, but apparently books have some sort of lasting impact.

Moreover, this will be a book that will be available, at least in chunks, on the Web.

Overall, I must admit, with a smile on my face, I get a bit peeved with all the suggestions of the form, "Why don't you do this?", where this is something entirely different than what I've proposed, and involves 10-100 times more work (and, in the case for example of putting out a TV show or DVD, at least 10-1000 times more risk in it actually being completed). My point is there is almost nothing like what I'm proposing out there. I say almost because Godel Escher Bach is still in print, and there are things like the Turing Omnibus (which, again, I think is for a more mature audience that I'm intending).

Small steps for baby feet.

Anonymous said...

I'm old-fashioned myself; if I didn't love books I wouldn't be in the profession I'm in. But my 17-year-old nephew (who wants to be a physics teacher) gets most of his information electronically, as do his peers. He likes books, but they are never his first stop on the road to enlightenment. How are you going to make him and others like him take the next step of reading your book? Creating interest through a TV show is the highest-profile way of doing this. I didn't mean to suggest in my previous post that this is something you personally should coordinate but it is something the members of the ACM should be pushing the society to do. And surely there are some among you who would not object to being a talking head of the Brian Greene kind?

Getting back to the book alone idea: I'm aware that writing a book is substantially less effort than doing any kind of electronic thing. But it isn't a small amount of effort. If you want even this non-trivial effort not to be wasted, you need to do some market research and enlist allies, which includes checking out the activities of the NCTM and the relevant sections of the ACM. I've had some experience trying to market books for "smart high school students" and it's practically impossible to do this directly. You have to choose an intermediary audience to sell the book to and hope for a trickle-down effect. This is where TCS has an advantage over other areas of CS in that you can present yourselves as an extension of mathematics.

Or you can go the mass-market route, in which case you'll have to hope that parents will read the book and be inspired to hand it on to their kids. But in that case, as Paul rightly points out, you'll need some kind of personality or other hook and a lot less actual mathematics. I don't have the impression this is the kind of book you are envisioning. And as a raising-general-awareness strategy, the mass market book is a good one, but as a trickle-down strategy it's risky. I know a lot of people who recently read "The Indian Clerk", but I suspect relatively few of them have recommended it to a teenager.