Rock and TCS

Janos Simon and Luca Trevisan are reporting from FOCS 2006 (Berkeley, CA)---a conference from which our community is, alas, conspicuously absent---on the Complexity Blog and on In Theory, respectively. Their live reports make for very interesting reading. I encourage you to read Janos's report on the FOCS Business Meeting to get an idea of the state of funding for TCS in the US.

One of the events at FOCS was a concert by Lady X and The Positive Eigenvalues, a band that includes Christos Papadimitriou on keyboards. As Luca Trevisan notes in his blog, apart from Christos Papadimitriou, Mike Jordan, and guest star Anna Karlin, that band includes "a number of other Berkeleites (for some reason, all Italians)."

This is not the first ever example of a rock concert held at a major theory conference. I recall that Dexter Kozen and his band performed at the Monterey aquarium during LICS 1989. Amongst others, they offered (T)CS renditions of songs by the Ramones (I wanna be promoted) and the Dead Kennedys (Categories über alles). At the time I collected a leaflet with the text of the songs Dexter's band played, but I lost it. Here is a scanned version of the leaflet, courtesy of Don Sannella. Enjoy it!

Report on NWPT06

Anna and I organized the 18th Nordic Workshop on Programming Theory from Wednesday, 18 October, till Friday, 20 October, at Reykjavík University. The workshop was held under the auspices of the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS) and of the IFIP TC1 Working Group 1.8 on Concurrency Theory, and was partly sponsored by Reykjavík University.

The NWPT series of annual workshops is a forum bringing together programming theorists from the Nordic and Baltic countries (but also elsewhere). The previous workshops were held in Uppsala (1989, 1999 and 2004), Aalborg (1990), Gothenburg (1991 and 1995), Bergen (1992 and 2000), Turku (1993, 1998, and 2003), Aarhus (1994), Oslo (1996), Tallinn (1997 and 2002), Lyngby (2001), and Copenhagen (2005). Thus, this was the first ever NWPT workshop held in Iceland.

The event was attended by 45 scientists from the Nordic countries, but participants came from as far as south as Italy :-) In addition, several local MSc and advanced BSc students enjoyed some of the presentations, which were of consistently high quality. (Here are a couple of quick observations on the geographical distribution of the participants.

1. There were no contributed talks from Sweden, and David Sands was therefore the only representative of Swedish computer science at the workshop.
   
2. There was a good number of participants from Germany.)
   

The scientific programme consisted of four invited presentations and 26 contributed ones. The four invited talkes were:

• Gerd Behrmann, Aalborg University. How to become a successful tool builder - the dirty tricks
• Matthew Hennessy, University of Sussex. Some Remarks on Testing Probabilistic Processes.
• Hanne Riis Nielson, DTU. Analysis of Process Interactions
• David Sands, Chalmers University of Technology and University of Göteborg. Specifying and Verifying Dynamic Information Flow Properties

Hanne Riis Nielson gave the workshop the best of starts by offering an excellent overview of her work on using static analysis techniques to validate models of computational scenarios vis-a-vis the actual "reality" that is being modelled. As a motivating question she asked: "How can we be sure that process calculi descriptions of, say, biological processes/pathways are faithful to reality?" At the end of her clear and well-paced lecture, the audience was left feeling that static analysis can indeed help in addressing the all important motivating question underlying her presentation.

Gerd Behrmann's talk offered a thought provoking and stimulating analysis of the role of tool development in algorithmic verification. Gerd gave the audience many good reasons for building tools, but also pointed out that empirical studies in this field are often of questionable quality, with results that are not reproducible and unfounded conclusions. He pledged for this situation to be improved if tool building is to become a respected scientific activity.

Not surprinsingly, Gerd's talk gave rise to a lively discussion (both during and after the presentation). Flemming Nielson made some very interesting remarks after the talk, explaining how a tool developer can obtain credit for his/her work at his institution (DTU), e.g., by means of innovation schemes and the writing of books about the lessons learned during tool building. He also defended, in case there was any need to do so, the hard work of theorists, and uttered the following eminently quotable sentence:

"The purpose of theory is insight, not theorems!"

Matthew Hennessy delivered a talk on testing probabilistic processes that presented work he did while visiting NICTA in Australia. This was a one hour version of a shorter talk he had delivered earlier at the symposium in honour of Gordon Plotkin's sixtieth birthday. Matthew gave a typically well polished lecture, which managed to present a lot of technical work without ever giving his audience the feeling of being overwhelmed by the mathematics. I am looking forward to reading the paper on which the talk was based.

The last invited talk for the workshop was delivered by David Sands. Static verification of secure information flow has been a popular theme in recent programming language research, but the information flow policies considered are based on a static view of security levels. In his talk, Dave provided a road map of the main directions of current research, and introduced a simple mechanism, called flow locks, for specifying dynamic information flow policies, and a type-and-effect system for statically verifying flow lock policies. The talk was based on joint work with Niklas Broberg.

The 26 contributed talks were mostly of excellent quality, presenting work at different stages of development; some of it was definitely in progress, some other was "in infancy", and some was instead very mature. This is what a workshop should be like!

Some photos from the workshop, courtesy of MohammadReza Mousavi, are available.

The 2007 edition of the workshop will be held in Oslo, Norway. I trust that it'll be just as successful as we felt this one was. Good luck to Olaf Owe, who will take over the mantle of organizer from Anna and me.

Double Blind Refereeing

A colleague of ours was discussing the following dilemma with Anna today.

A computer scientist is preparing a submission to a conference in Language Technology that has double blind refereeing. He is just about the only person in the world doing tagging for Icelandic. Should he cite his own work in the submission?

This colleague realized that, by citing his own work, he would make his identity known to the reviewers, and was worried that this might influence them. We told him that a reviewer would be able to infer the name of the author from the paper anyway because he is really the only possible author of that paper. (In general, in TCS the set of possible authors of a paper is not very large, and, using tell-tale stylistic or notational usages, a reviewer of an authorless paper is often able to determine the author(s) of a paper with a rather large degree of accuracy.)

Consider also the following catch-22 situation. A reviewer of the paper by our colleague could reject it because the anonymous author X is neither citing the closely related work of author X nor comparing his work with that of author X! It would be just great to have one's paper rejected for not citing one's own work, wouldn't it?

I have never believed in double blind refereeing. This story has reinforced my lack of belief in this system.

Mini Course on Model Checking Real-time Systems in Reykjavík

As part of the ICE-TCS activities held during the coming week, which will be mostly devoted to the 18th Nordic Workshop on Programming Theory, we shall host a mini course Model Checking for Real-time Systems held by Kim G. Larsen. The course will be held on Monday, 16 October, at Reykjavík University. (In case you are interested in looking at some text in Icelandic, you can see the announcement that will appear tomorrow in one of the local newspapers.)

The course will be followed by an exercise session on Tuesday, 17 October, held by Alexandre David (Aalborg University). Feel free to drop by, if you happen to be in Reykjavík for the Iceland Airwaves music festival.

Teaching Reductions

This semester I am teaching Introduction to the Theory of Computation at Reykjavík University, a course taken by third year BSc students and MSc students alike. I like teaching this course (based on Michael Sipser's book bearing the same title) very much, and I try to convey to the students the intellectual excitement I feel about the theory of automata, computability and complexity.

After last Wednesday's lecture, however, I was totally drained of energy. Why? During Tuesday's lecture I introduced the concept of reduction, and used it to prove the undecidability of the emptiness, equality and regularity problem for Turing machines. The day after I started the lecture with a warm-up, peer instruction session asking the students to argue that it is undecidable whether a Turing machine accepts the language {Alan, Turing}. The reaction was summarized by the blank stare I got from most of my audience Even when we worked through the solution together, I still had the feeling that many of them were not comfortable with the notion of reduction. I had to work very hard to try and clarify it as best as I could, and it is not clear to me yet whether I succeeded.

Looking back to my previous experiences teaching this course, or variations on it, in Aalborg, this is not surprising. The notion of reduction is the bread-and-butter of computability and complexity, and one of the cornerstones of algorithmic thinking. Having mastered it, the rest of the material in my introductory courses becomes, I would venture to say, relatively easy. It is one of those powerful concepts that opens up new vistas, and, despite being very natural and ubiquitous in the theory of computing, requires some intellectual maturity to be understood fully.

A typical pitfall I have experienced over the years is that many students think that the pre-processing algorithm converting, say, the question "Does a Turing machine M accept the string w?" into an equivalent one of the form "Does the Turing machine M' accept the empty language?" actually runs M on input w when, while producing the code for M', it writes the line of code

Run M on input w.

Here I usually use the analogy with a compiler to try and dispel their doubts. (Basically, I tell them to view the pre-processing algorithm implementing the reduction as a compiler between inputs to two different problems. The pre-processing algorithm outputs a piece of code, but never runs it.) It is not up to me to say whether this works, but it seems to me that most of the students "crack the code", and start thinking naturally in terms of reductions between algorithmic problems.

Is it just my personal experience, or are reductions hard to grasp for many of our students? I'd be happy to hear how you go about teaching reductions in your classes on the theory of computation, and what analogies/metaphors you use to help your students understand such a fundamental notion.

Turing in the Notices of the AMS

The November issue of the Notices of the AMS is entirely devoted to Alan Turing. (I first learned about this issue via Luca Trevisan's blog in theory.) I have only had time to skip through Solomon Feferman's piece on Turing's thesis (his PhD thesis, not the Church-Turing thesis), but the whole issue looks very interesting.

I have already recommended it to the students who are taking my theory of computation course in Reykjavík.

Enjoy it!

Paul Halmos, 1914-2006

I just saw a sad news item on the AMS web site. Paul Halmos passed away on Monday, 2 October. He was a master of mathematical exposition, both in writing and speaking, and taught many writers in the mathematical sciences how to write.

A few years ago, I had the pleasure of borrowing his "mathobiography" I Want to Be a Mathematician from Steffen Lauritzen in Aalborg, and enjoyed it immensely. I plan to buy a copy for my bookshelves at some point.

Bas Luttik has keeps telling me to read Halmos's expository work on algebraic logic. I keep postponing doing so, but maybe now it is time to start. At least after some pencil sharpening has taken place :-)

Let me end with a quotation from Halmos's mathobiography I like:

"I love to do research, I want to do research, I have to do research, and I hate to sit down and begin to do research---I always try to put it off just as long as I can.
....Isn't there something I can (must?) do first? Shouldn't I sharpen my pencils perhaps?"

- --Paul Halmos, I Want to be a Mathematician

These days I sharpen my pencils a lot, alas.