Category Archives: CS

Façade

I heard an interesting talk yesterday by Michael Mateas who’s a computer science professor at U.C. Santa Cruz who works on developing tools to create interactive narrative. I’ve heard people talk about interactive narrative from a Media Studies or English perspective, but it was interesting to here about it from someone who is trying to work through all the gory technical details to make it happen. There’s a lot of tricky AI to make a character seem believable. He talked about the challenges of making characters that react to player input while still maintaining long term goals in order to shape the narrative.

The main project he described is Façde, a psychological drama in which two of your old friends reveal their unhappiness with married life. The game is different every time you play it, and it’s interesting to try different things and see how the characters respond. I think the biggest problem at this point is the natural language understanding system. You can type arbitrary English, but I was left unsure how much of what I typed actually made a difference. Still it’s definitely worth the download.

Courses and Such

I’ve spent most of the week being oriented and trained, and I’m finally ready to start real work. I’m still waiting for a grad student to return from Yahoo before getting too involved in my research, but at least classes have started. My probable course schedule is

  • Analysis of Algorithms (with Dexter Kozen)
  • The Structure of Information Networks (with Jon Kleinberg)

Advanced Programming Languages looks really good as well, but I think it’s going to have to wait until next year.

In search of a Freaky Computer Scientist

Steven Levitt, author of the phenomenally successful Freakonomics spoke on Friday at Carleton. He talked about several problems he has looked at recently, including tracking terrorists using bank accounts and a recent experiment dealing with altruism. While I would have liked a bit more rigor in the presentation, there is no question that he knows how to work a crowd and get people excited about applying economics to everyday problems.

Levitt has been partially credited with changing public perception of the “dismal science,” and I must admit that I spent much of his talk thinking about how computer science, and particularly theoretical computer science, could use its own PR person. In most people’s minds computer science is exclusively about computers, and too many of them think that a degree in CS makes one a Microsoft Office wizard or a tech support guru. Even those with more knowledge of the field often see computer science as fundamentally linked to programming, and even many computer science students see theory as a useless pursuit with no applications to the real world.

I would argue the opposite, of course. I love programming, but what excites me the most about CS is the fact that, like math, it is so universally applicable. Algorithms are such a fundamental idea, that their potential applications are almost impossible to enumerate. Traffic analysis, airline scheduling, and genetic sequence alignment are all classic and common applications of algorithm design, and even the terrorist tracking problem that Levitt discussed can be seen as a computer science problem. In some sense he was trying to develop an algorithm to identify potential terrorists from bank records, and then he looked at how money flowed through that person’s social network. Being a theoretical computer scientist means that you can work in wide variety of application areas while doing basic research, and that seems like a pretty attractive combination.

I always think of a mathematician turned biologist who I met at DIMACS over the summer. She talked about how nice it was to be the biologist who knew math, because she got to work on so many different problems for other people. She gave a talk on bees, for instance, and quipped that some of her colleagues had made a career changing move from bees to wasps. By focus on the mathematics that underlies a lot of biology, she was able to work in a wide variety of interesting application areas, and that was one of the reasons she found her work so exciting.

I hope that some day soon a theoretician will take it upon themselves to write a Freakonomics-style account of theoretical computer science and its applications. There are a lot of bad popular science books out there, but the success of Levitt’s work gives me hope that there is a market for a well-written account of algorithm design and analysis. I think that such a book is an important first step in gaining mindshare as a legitimate and relevant academic discipline.