Why I Blog

There's a new meme making its way through the blogosphere that I think I will indulge myself with. Although I have not been tagged (as usual) for the "Why do I blog" meme, I have come across it in a few different spots such as Aetiology and A Blog Around The Clock. This meme seems to me to be spreading more slowly than other recent memes, perhaps because the reason why people blog is often self-evident from their blogs themselves. Having said that, I can see at the Blog Meme Tracker that it has been spreading. (One problem with that page is that it doesn't seem to have any facility for adding 'dotted line' links for people like me who weren't officially tagged.)

I actually had a rather specific purpose in mind when I started this blog, so maybe this post will help focus my attention back on that goal. It is said that the best way to test, or reinforce, your understanding of a subject is to explain it to someone else. My hope was that by explaining computability and complexity theory in this blog as I worked through the material, I would force myself to understand the material at a deeper level.

It would also serve a secondary interest I have in pedagogy. One thing I've found while trying to self-instruct from reading textbooks is that often the most frustrating stumbling blocks are the most superficial. I probably spend more time trying to decipher unfamiliar notation than I do with trying to grasp concepts. In fact, although there certainly are some very deep and difficult concepts in TCS, a lot of the material would be quite intuitive if only it was taught in a more concrete fashion. A big part of the problem is that textbooks are not generally meant to be used in isolation; something that might take an hour to parse while reading a text can often be explained away in a minute or two by a knowledgeable teacher in the classroom. So another goal I have with this blog is to explain the things I'm learning in such a concrete fashion that, say, a motivated high-school student could understand it.

As an aside, I've noticed some other bloggers touching on pedagogical issues recently... Bill Gasarch talks about teaching binary search to 8-year-olds. More ambitiously, Andy Drucker ponders teaching topology to kids. Much more ambitiously, Andy has also been working on simplifying the exposition of the PCP Theorem. This latter item is definitely not for kids. I don't know the PCP Theorem, and by that I mean that I do not even understand the statement of the theorem. (I know there are relatively simple "high level" explanations of the theorem, but I am not convinced that they really get to the meat of the theorem.) This might actually be a good end goal for this blog: If I can learn the PCP theorem, and explain the proof here in terms that a high-school student could follow, then I'll know it's time to quit! (I am assuming this will come after I prove that P ≠ NP.)

I've drifted away from my goals with this blog. The main reason for this, I think, is that my usual mode of discourse is to respond to other people instead of initiating the conversation myself. As a result, I've been spending my on-line time mostly by reading and leaving comments on other blogs. (I don't often provoke responses from others, so I sometimes wonder if anyone ever reads those comments... I have to add a thanks here to Joshua at The Adventures of Tobasco da Gama for the positive acknowledgment!) But blogging is all about initiating the conversation, so this is something I am going to work on. I'm also going to try to stay a little more focused on the goal, instead of getting distracted by all those other shiny objects on the Web.

Now for our little exercise in distributed peer pressure. I'm not sure if I know 5 different people who read this blog, but let me at least tag a couple of people. Let's see... I'm too late for Tyler, but I can still tag Foxy. And Antztein, you're being worse than me with your posting--consider this an excuse to make another entry. I know she won't see this, but since I'm sure she's been thinking about it, I'll tag Kathy Sierra. Okay, Kathy, now you have to post again since you've been tagged. And to anyone else out in the aether reading this, consider yourself tagged too.

Kids and TCS

I'd like to follow up on a comment to my last post, on looking for a book describing the math behind Sudoku.

Anthony Widjaja To asked the following:

... I have noticed several postings in the blogsphere (including your blog, Suresh's, and Lance's) on how to popularize complexity theory to general audience. I am interested in something related: how to get kids interested in math and science (including computer science, physics, or even cosmology). These days many kids are spoiled by video games, etc. leaving very little room for curiosity about math and science. Since you have kids and are interested in a related issue, I'm sure you have some advice or pointers to useful discussion.

Well, I'm not sure if I have any useful advice about this, but let me mention a couple of things, which I think apply to math and science generally as well as to TCS in particular. First off, I feel that the question of how to get kids interested in TCS and how to get the general public interested in TCS are one and the same. That is to say, I think the only way to get the general public interested is to get kids interested, and then wait for them to grow up. I strongly suspect that the people who made up the audience for the various specials on Einstein this past year, or who buy up books like Brian Greene's The Elegant Universe, first became interested in the subject as kids or young adults. You may be able to get a few converts later in life, but not enough to make a significant difference.

Now having said that, I do think it's possible for TCS in particular to gain "market share" in the general public by stealing some interest away from those physics and cosmology fans. To do that, it needs to position itself a bit differently. I think that what attracts laypeople to physics and cosmology is that it seems to address some fundamental questions about what our place in the universe is. Practitioners in TCS need to occasionally step back from their narrow research interests and look at "big picture" questions of what is computation, what is information, what are the formal limitations of knowledge, why are some tasks inherently difficult -- and then write about these topics for a general audience. Sure, there are a few books like that on the market already, but it's purely a matter of numbers: For every Elegant Universe, I'm sure there are hoards of obscure physics books that nobody reads. Conversely, if you want to see another, say, Gödel, Escher, Bach, then you've got to start cranking out TCS books until you get a winner. This is not meant to suggest that the success or failure of a book is a matter of chance, but rather that it's not knowable in advance who's going to make a great author. So everyone should be encouraged to write at least one book for a general audience.

As for how to get kids interested in computing, my own kids are still a little young for me to have experimented on personal experience with. But I think a couple of points are clear. First, you have to start young enough, as soon as students are old enough to grasp concepts like what an algorithm is. This should happen by middle school or junior high. I think this is particularly important for getting girls interested in computing. Second, you need to hold students' attention by tying computing to other topics they're interested in. The undecidability of the halting problem is going to grab a certain type of student, but for others it is going to be too dry and abstract. Fortunately, computing has direct application to such a wide range of topics that there ought to be something for everyone. Case in point: I was checking the server stats for this blog, and the most popular search keyword so far this month is (you guessed it): sudoku.

There are educational standards that have been developed by various professional organizations. For example, the Computer Science Teachers Association was formed by the ACM to promote K-12 computer science education. They have a model curriculum that schools can use as a guide. The Mathematical Association of America promotes mathematics education at the college and grade-school levels and obviously will include topics relevant to computing. Unfortunately, model curricula probably aren't going to help too much with the question Anthony had in mind. Here is something aimed at young students that looks pretty neat, Computer Science Unplugged. I just bought a copy of this book and will let you know what my impression is once I have a chance to play around with it.

What I would really like to see are some web sites designed to teach computing to young students. Math and computer science are ideally suited subjects for on-line instruction, and you'd think there would be some real kick-ass web sites out there to do just that. However, the sites I've seen so far have been pretty lame. This is something that the ACM/CSTA, with its combination of an interest in pedagogy and technical expertise, ought to be taking the lead in.

Finally, on a personal level, the way to get kids interested in computing (or science or math) is by setting an example. If the children around you see that you find these subjects interesting, they will be more likely to explore them at some point. (And for this strategy to work, you have to begin when they're very young, before they start using you as an example of what not to do.)

Math and Sudoku

Welcome to 2006! I hope everyone had a cheery holiday season.

I posed the following query on comp.theory but haven't gotten any responses at all, so I thought I'd see if I can get any feedback here. (In the past when I've posted some really dumb questions on comp.theory, I've received lots of replies; there seems to be an inverse relationship between the volume of discussion and the meaningfullness of it. So maybe my current question is not so bad.)

My niece has become interested in sudoku, and this interest has spread to my own children. I was thinking that sudoku would make a nice jumping-off point to introduce topics in discrete math and complexity theory. Are there any books out there that deal with this? I haven't been able to find anything. Ideally, such a book would be geared toward a teen-aged audience and maybe cover topics like combinatorics, logic, and NP-completeness as they apply to sudoku. A quick Google search reveals lots of web sites that touch on this stuff, so maybe it's just too new an area to have made its way to print yet.

I'm reminded of some of the discussion following FOCS '05 about how to get complexity theory into the public awareness. It seems to me that tying it to a subject that's already popular with the general public would be one way to achieve this.

Any thoughts? I know David Eppstein has an interest in sudoku; I wonder if he's ever considered writing something like this. Or maybe I should think about writing this myself? I'm grossly unqualified, of course, but that might actually be an advantage--it could make it easier to understand the point of view of a general audience and anticipate the hard spots when explaining concepts.

How I became a theory dilettante

In a recent blog entry, Lance Fortnow describes how he became a theorist. It seems that he started out in college as an engineering student, but switched to math because he was turned off by the, uh, pragmatism of engineering. But it was an introductory TCS course by Juris Hartmanis that really set him down the theory path. In a response on his blog, Suresh describes how he came to TCS by way of AI.

During my first couple of years of college, I tried a number of different subjects including engineering, but ended up in math because I couldn't really decide on a particular discipline. I figured that with a math background, I would be able to do pretty much anything after I left school. I had always had an interest in computers and programming, but more along the lines of numerical analysis than TCS. Computing was a tool for carrying out mathematics and not the other way around.

I did take an introductory TCS class in my junior or senior year that was offered by the math department. (The CS program at my school was run through the engineering department, so this was something apart from that.) Unfortunately, the course killed any interest I had in TCS. The text we used was An Introduction to the General Theory of Algorithms by Michael Machtey and Paul Young, which has a very abstract, recursion-theoretical feel to it. Although the text did include an introduction to complexity theory, our course was pretty much limited to computability. The subject seemed to me to be totally detached from any practical applications for programming. It was pretty dreadful.

I was, however, interested in AI after reading Douglas Hofstadter's Gödel, Escher, Bach: An Eternal Golden Braid. But the more I read up on AI, the more it seemed hopelessly unable to explain what intelligence (or consciousness) was, and that it would probably stay that way during my lifetime. So after a while I lost interest in AI as well. (By the way, I no longer feel this way about AI. I am very excited by the approach outlined in Jeff Hawkins' book On Intelligence.)

After graduating, I eventually wound up working as a programmer for an insurance company. But I missed the collegiate environment, and one day I noticed an ad by University Video Communications for a series of videotaped lectures on various topics in computer science. I ordered "The Shortest Network Problem" by Ronald Graham, and was immediately hooked on the question of P vs. NP. In the lecture, Dr. Graham gave as a reference the Garey and Johnson text Computers and Intractability: A Guide to the Theory of NP-Completeness, which I ran out and purchased from my local bookstore.

Now, studying this kind of material on one's own is not particularly easy, and I probably wouldn't have gotten very far with it had it not been for the other big influence at that time: the Internet and the World Wide Web. Being able to interact with others over the net, as well as being able to access scores of TCS web sites has made an incalculable difference in learning this subject.

I need to mention one other important influence. There are hundreds of introductory theory of computing textbooks out there, many of which are excellent. But it is hard for me to imagine learning this material from anything other than Michael Sipser's Introduction to the Theory of Computation. This book has made learning TCS fun.

That is where the story ends, which is why the title to this entry reads the way it does. For now this is just a hobby for me. Perhaps one day that will change, and then I can write about "how I became a theorist".