The chapter was designed to cover what I think are important features:

- A simple introduction, based on (hopefully) easy-to-follow examples.
- An explanation of why this is important in "the real world".
- Important past results, that are known and understood. (Here, Reed-Solomon codes and LDPC codes.)
- A goal for the future. (In this case, network codes, and figuring out how they might actually be used in networks.)
- Links/pointers to relevant references.

Other questions:

1) Why not do it in a wiki?

Answer: I've explained some in comments-- I don't think a wiki is appropriate for a "creative writing" exercise. Also, I'd like some actual commitment from authors, and I'd like them to get credit for their work. (If this all works out, you can put this on your next NSF grant application as your broad educational service.)

2) Why focus on "theory"?

Answer: It's that perfect/good thing. I'd like something coherent, that I'm qualified to manage, that can be done in a reasonable time frame. That means some focus, and I'm choosing to focus on theory. (And theory, in my mind, needs the PR.)

If this works out, we can expand to other volumes. Heck, I'll manage/edit volume 2, communications and networking. Then I'll hand it off to someone else.

3) Who do you want to volunteer?

Answer: I'll be honest -- I have a very strong preference for Ph.D.'s (over graduate students), and I'd generally prefer "name" professors/research scientists -- we need at least some of those, so we can start developing some of that cult of personality in our field, and so the book will carry some weight with publishers and other outsiders. But I'd be open to any and all good ideas.

4) Timeline?

Answer: Well, I'll talk about "management" more next post. But I'd hope that a dozen or so people could be convinced to take some time over the summer -- maybe a week or so -- and write up a chapter draft. But since last time that sort of schedule seemed too optimistic, I'd be thrilled to get chapters by the end of the year....

Next post: ideas on management?

## 9 comments:

I'm curious about the range of subjects you'd like to see included. How broad of a net are you using to define "theory"? I'm assuming that it would include machine learning and AI ... what about things like programming language semantics, or database theory? If you posted a list of proposed topics it would undoubtedly generate some interesting discussion here.

Programming language semantics are closer to theory than a lot of AI. The problem, of course, is that the entire field is ungodly boring!

But certainly:

Cryptography

Learning Theory

Game Theory

Complexity Theory

Approximation Algorithms

all have the potential to lend themselves to sexy chapters and captivating problems.

I wonder if this is the right way to think about the problem you are trying to solve. Do it this way and you will wind up with the framework for the theory quals (of schools that, unlike Harvard, actually have theory quals). You're not actually trying to crate a foundation on which a superstructure can be built, nor to visit all the squares of a neatly stitched quilt. You are trying to get students to say OK, I get the problem, dunno how to solve it ... Wow! that's really neat! I wonder what else there is like that?

So maybe you'd be better off thinking of PROBLEMS first, problems anyone can understand and have "elementary" solutions but have the characteristic that solving them exposes interesting principles. You may have to pause to develop some substructure on the way to the solution, or you may solve the problem and then explain the generalized structure later. Some areas, such as PL semantics, might get omitted entirely because there are no problems you can state to a 15 year old that are likely to seem natural.

Something I keep wondering when I see your posts on this subject: have you seen Dewney's

The (New) Turing Omnibus? How would your project differ from that book?D. Eppstein (for some reason locked out of OpenID today)

Here's a problem - let's say you have codes to launch a nuclear missile. You'd like to divide the codes between two people, so that neither one can launch the missile alone. (Think the opening scene from WarGames.)

How do you do it?

Answer: draw a line that crosses the Y-axis at the coordinate equal to the launch codes. Give each person one point on the line.

Can then bring up issues of how best to represent "points" and "lines" on a computer. This leads to secret sharing over finite fields, which ties into the Reed-Solomon codes you described in the sample chapter.

Harry --

I agree with your sentiment. The point of what I'm aiming for is not to cover every area of CS (or even of theory). It's to spark that curiosity.

I guess I just think there are problems in most areas of CS (and in particular TCS) that are interesting. I'm not interested in starting with problems. I'm interested in starting with

people-- people who think they have something interesting to write about and who are interested in writing -- and I assume that the exciting problems will come from there.So I don't want to make a laundry list of "topics to covered". (Though, from my own personal bias, of course I think there are topics that are really exciting and should be covered.)

anonymous -- I just looked at what I could of the Turning omnibus online. It looks cool. But it looks much more mathematical/deep than I'm expecting. From my quick peek, it looks like it's at the level of college sophomores (in particular, college sophomores who have probably had some CS already!). I'd like to aim for high school sophomores.

I think there are completely untapped markets you haven't mentioned. By aiming at high school sophomores you are writing at a level that is accessible by anyone vaguely interested in the subject. This includes leagues of business people, older engineers, and those generally interested in problem solving. Lastly, as a graduate student, I would probably grab a copy for my parents to better explain my interests in the form of interesting/meaningful problems. By increasing the general awareness of problems computer scientists are interested in, you still will likely achieve your goal of attracting younger people to the field. Personally I believe explaining the subject via analogy to everyday problems (e.g. TSP) you can make it accessible to many. If you would like a small audience of potential high school students I would be glad to help where possible.

High school sophomores can be highly perceptive if you give them a problem that is meaningful. I had to work on some trigonometry homework problems with my niece (HS Junior) a couple of weeks back.

I wrote something similar to this on Isabel's blog the other day. The idea is that you start with an interesting problem, construct the meaningful abstractions, reason about them, then come back to answer about your concrete problem.

In this case, if you want to encourage kids to investigate and understand theory, it might be useful to construct a problem, derive the abstractions, then map those abstractions to [same|[near|not] similar] problems. This demonstrates the two important things, bijective abstract-concrete reasoning, and the importance of looking for the abstract [refactoring your comprehension base].

Post a Comment