The Value of a PhD

I recently stumbled across the blog The Unapologetic Mathematician, and read this post. Its title suggests that it is about commencement exercises, one of those, admittedly rather boring, academic rituals that get perpetuated every year. In reality, the post waxes lyrically about the "value" of a PhD.

As will be clear to those of you who read that piece, the "unapologetic mathematician" can write! For what it is worth, I agree with what he says. Here is an excerpt I really liked.

The doctorate is the gold standard of the academy. You can’t get it by spitting back answers on a sequence of course finals. You can’t get it by retaining the material until a collection of comprehensive exams, or by writing up a survey of relevant literature. You attain a doctorate by extending the boundaries human knowledge.

This society generally speaks well of originality, but it tends to mean a rather pale sort. To really, truly think of something nobody else has before — and to be able to justify it — is really far more difficult than most people give credit to. It’s not something you do on weekends, in your spare time while doing other more important things. The Great Work is hard. It means steeping yourself in a subject until you understand in a way only a handful of other people do. It means sacrificing years of your life to the pursuit of something truly new and different. The path is littered with those who started and did not make it through to the end.

And it has no justification but itself. Nobody goes into academics for the money. Nobody does it for the praise of the masses. Compared to most other things any of these new doctors could have done it will be temporally thankless. You live the academic life because you look outside at the amazing world around yourself and you realize that, for you, the highest achievement of the human spirit is to understand it more deeply — to internalize some aspect of it, digest it, and help share that with the rest of humanity. You do it because it is fundamentally worth doing. The life of the mind has a value in and of itself. And so these men and women have chosen this value over all the others they might have.

Amen. In a society where money is the only thing that seems to matter, and where any line of study carrying one or more of the tags "business", "financial" or "media" attracts hundreds of students, it is good to see somebody sing the praises of adding a little to the honour of the human spirit.

A Journal Without Editors

Here is another bit of trivia related to publication issues. The latest issue of the Elsevier Journal "Topology" has appeared without any mention of an editorial board. (The page that normally lists the editors is blank.) I looked at the home page for the journal, and there is no mention of editors there either. The guide for authors states

"For information regarding current submissions please contact topology@elsevier.com. "

As you probably know, the entire editorial board of Topology resigned last year. (The resignation letter is available here.) The board has founded a new journal, Journal of Topology, published by the London Mathematical Society and Oxford University Press. The price of the journal will be roughly one third of the price of the Elsevier journal.

Second ICE-TCS Annual Report

Magnus M. Halldórsson, Anna Ingólfsdóttir and I have been co-directing ICE-TCS, a small research centre in theoretical computer science, here in Reykjavík for two years. Our second annual report is now available, in case anybody is interested.

ICE-TCS operates on a shoestring budget, but we hope that the local funding agencies will become interested in investing in "centres of excellence" and that they'll consider ICE-TCS to be one of those. (Fat chance :-)) In the unlikely event that this happens, I'll announce available visiting positions on this blog. Watch this space.

The Wrecking of British Science

Harry Kroto is one of those larger than life figures whose life we are lucky to cross in our lives every now and again. He was a professor of chemistry at the University of Sussex when I was a PhD student there, and received the Nobel Prize for Chemistry in 1996 for his discovery of the C₆₀ molecule, aka buckminsterfullerene. He was the prime mover behind the Vega Science Trust, a UK educational charity (see www.vega.org.uk). He has been one of the participants of the heroes in science programme here at Reykjavik University, where he played with models of C₆₀ molecules together with local kids.

Why am I droning on about this guy, you may ask? The reason is that I just read this article he wrote for the Guardian. (I strongly recommend that you read it, especially if your heart still feels for the British university system like mine does.) The picture Kroto paints is bleak, but all too familiar, alas. Throughout the western world, the number of students interested in science is declining frighteningly, at a time when our society is so dependent on science. As Kroto writes in that article:

Scientific education is by far the best training for all walks of life, because it teaches us how to assess situations critically and react accordingly. It gives us an understanding based on reverence for life-enhancing technologies as well as for life itself. If we do not know how things work, how can we fix things? And how are we going to use these powerful technologies wisely?

The situation in universities is exacerbated by present policy, which actively encourages vice-chancellors who know the cost of everything and the value of nothing to eliminate science departments in favour of trendy, cheap courses. These VCs bleat about how important their freedom is to do whatever they wish with taxpayers' money, and steer funds earmarked for the sciences into softer areas that students prefer.

Just as cheap fast food has resulted in unprecedented levels of obesity, so this McDonald's approach to cheap, trendy, seductively soft courses designed for mass consumption in tertiary education has resulted in a plethora of students trained for non-existent jobs.

Even more important than the training for non-existent jobs is the worrying decrease in our society of that willingness to think critically, to work on problems, to be creative, and to challenge ourselves that are one of the main ingredients of our humanity. I sincerely hope that the new Icelandic government that was formed today will work proactively to put science on the agenda in Icelandic schools at all levels. It is a small step, but one has to start somewhere.

Elsevier's Computer Science Review

Wolfgang Thomas recently pointed out to me a new Elsevier journal by the name of Computer Science Review. The aim of this journal is to publish research surveys and expository overviews in computer science and related fields. The reviews are aimed at a general computer science audience.

I was not aware of this new Elsevier journal, and my feeling is that its aim overlaps somewhat with that of the columns in the Bulletin of the EATCS. As one of the column editors, so far I have been extremely impressed by the willingness of the members of the concurrency theory community to contribute to the Bulletin. However, when I read at http://www.elsevier.com/wps/find/journaldescription.cws_home/710138/description#description that

"Submissions are free of charge and recognizing the work involved in preparing a review article, Elsevier will pay authors for their contributions to Computer Science Review. This amount will be Euro 400 per accepted article for the authors; provided the article meets minimum length requirements (at least 20 typeset pages, preferably more). Book reviewers will be paid for comprehensive book review contributions - EUR 15 per typeset page, to a maximum of EUR 100." (The emphasis is mine.)

I cannot help but being worried about the future of the columns. Paying authors for their contributions to a journal is a remarkable development, and can even be seen as unfair competition :-) Sure, we are not talking about large sums of money, but I am not aware myself of any other journal in computer science that pays its contributors. Do you know of any journal that does so?

I wonder whether this move by Elsevier heralds a new era in which commercial publishers will reward authors, editors and referees financially. I am not sure that this would be a positive development myself. (Only once so far I have been "paid" for a journal review, and was very surprised when the cognizant editor offered to pay me. I received a 50-euro book voucher for reviewing a paper that had been awaiting a referee report for about three years and that, for some reason that I cannot understand yet, nobody wanted to evaluate.)

As Moshe Vardi often says, our currency is reputation, not money. Call me an idealist, but I'd like to keep things this way.

Comments on the issue of payment for journal papers, review articles and book reviews are most welcome. I'd really love to hear what you think about this new development.

Concurrency Column for the June 2007 Issue of the BEATCS

I have just posted the concurrency column for the June 2007 issue of the Bulletin of the EATCS.
In this piece, Orna Kupferman, who is one of the prime movers in the study of automata-theoretic constructions and in their application to the verification of reactive systems, presents a survey of several automata-theoretic problems in which the gap between the known upper and lower complexity bounds is exponential, and describes recent efforts to close the gaps.

I am glad to be able to offer this piece to the readership of the concurrency column and of this blog, and I trust that you will enjoy reading it as much as I did.

PCs for ICALP 2008

Over the coming year or so, I'll be using this blog to keep you posted on the developments in the organization of ICALP 2008, which Anna Ingolfsdottir, Magnus Halldorsson and I will be co-organizing at Reykjavik University in the period 7-11 July 2008.

ICALP 2008 will have three tracks, and the PCs for the three tracks have been formed. They are as follows.

Track A

• Michael Bender (State Univ of New York at Stony Brook, USA)
• Magnus Bordewich (Durham University, UK)
• Peter Bro Miltersen (Aarhus University, Denmark)
• Lenore Cowen (Tufts University, USA)
• Pierluigi Crescenzi (Università di Firenze, Italy)
• Artur Czumaj (University of Warwick, UK)
• Edith Elkind (University of Southampton, UK)
• David Eppstein (University of California at Irvine, USA)
• Leslie Ann Goldberg (University of Liverpool, UK) (chair)
• Martin Grohe (Humboldt-Universität zu Berlin, Germany)
• Giuseppe Italiano (Università di Roma "Tor Vergata", Italy)
• Christos Kaklamanis (University of Patras, Greece)
• Michael Mitzenmacher (Harvard University, USA)
• Ian Munro (University of Waterloo, Canada)
• Ryan O'Donnell (Carnegie Mellon University, USA)
• Dana Ron (Tel-Aviv University, Israel)
• Tim Roughgarden (Stanford University, US)
• Christian Scheideler (Technische Universität München, Germany)
• Christian Sohler (University of Paderborn, Germany)
• Luca Trevisan (University of California at Berkeley, USA)
• Berthold Vocking (RWTH Aachen University, Germany)
• Gerhard Woeginger (Eindhoven University of Technology, the Netherlands)

Track B

• Parosh Abdulla (Uppsala University, Sweden)
• Luca de Alfaro (University of California, Santa Cruz, USA
• Christel Baier (Technische Universität Dresden, Germany)
• Giuseppe Castagna (Université Paris 7, France)
• Rocco de Nicola (Università di Firenze, Italy)
• Javier Esparza (Technische Universität München, Germany)
• Marcelo Fiore (University of Cambridge, UK)
• Erich Grädel (RWTH Aachen, Germany)
• Jason Hickey (California Institute of Technology, USA)
• Martin Hofmann (Ludwig-Maximilians-Universität München, Germany)
• Hendrik Jan Hoogeboom (Leiden University, NL)
• Radha Jagadeesen (DePaul University, USA)
• Madhavan Mukund (Chennai Mathematical Institute, India)
• Luke Ong (Oxford University, UK)
• Dave Schmidt (Kansas State University, USA)
• Philippe Schnoebelen (ENS Cachan, France)
• Igor Walukiewicz (Labri, Universitè Bordeaux, France) (chair)
• Mihalis Yannakakis (Columbia University, USA)
• Wieslaw Zielonka (Université Paris 7, France)

Track C

• Christian Cachin (IBM Research Zurich, CH)
• Jan Camenisch (IBM Research Zurich, CH)
• Ivan Damgård (Aarhus University, Denmark) (chair)
• Stefan Dziembowski ((Università di Roma "La Sapienza", Italy)
• Dennis Hofheinz (CWI Amsterdam, the Netherlands)
• Susan Hohenberger (Johns Hopkins University, USA)
• Yuval Ishai (Technion Haifa, Israel)
• Lars Knudsen (DTU Copenhagen, Denmark)
• Arjen Lenstra (EPFL Lausanne, CH)
• Anna Lysyanskaya (Brown University, USA)
• Rafael Pass (Cornell University, USA)
• David Pointcheval (ENS Paris, France)
• Dominique Unruh (Saarland University, Germany)
• Serge Vaudenay (EPFL Lausanne, CH)
• Bogdan Warinschi (Bristol University, UK)
• Douglas Wikström
• Stefan Wolf (ETH Zurich, CH)

The call for papers for the conference will be available by early July this year, and will include the names of at least two invited speakers. Watch this space for further information.

For the moment, plan to submit your best papers to ICALP 2008 and use this chance to make a visit to Iceland and to our ICE-TCS research centre!

The End of an Era

Last Friday I heard from Wan Fokkink that Jaco van de Pol will become a professor in Twente after the summer (as a successor of Ed Brinksma, who is now the director of the Embedded Systems Institute in Eindhoven). Congratulations to Jaco.

A byproduct of Jaco's move to Twente is that the process algebra group at CWI, which over the years has been headed by Jos Baeten, Frits Vaandrager, Jan Friso Groote, Wan Fokkink, and finally Jaco van de Pol, will be terminated. It is a fact of life that all (good) things must eventually come to an end, but I cannot help but feel that this is truly the end of an era.

The work of the process algebra group at CWI has played a major role in my scientific development, and I have had the pleasure to collaborate on various projects with several of its leaders mentioned above. (Disclaimer: The process algebra group at CWI is not responsible for the outcome of my work :-)) I like to think that the legacy of that group will be felt for many years to come. Indeed, one of the signs of its impact on Dutch computer science is the fact that all of its leaders over the years are now professors and leaders of strong research groups in some of the best Dutch universities.

Even though my work owes a lot to the intellectual inspiration of the process algebra group at CWI, I only visited CWI once in September 2005, and then only for a day to deliver a talk in the well-known PAM series---well, well-known amongst process algebraists. I guess that this indicates how little I travel around, and that one can be influenced by the work carried out at an institution without having ever visited it. (As another example, I owe a great debt to the Edinburgh concurrency school, but I have never visited Edinburgh.)

I vividly recall that, while introducing my talk at CWI, I paraphrased a famous sentence by the Italian writer Alessandro Manzoni and said that I felt that I had finally gone to Amsterdam to wash my process algebra clothes in the Amstel. With the demise of the process algebra group at CWI, it will unfortunately become a lot harder to wash my process algebra clothes in the Amstel.

What is Time?

When studying process algebras for the description of timed behaviours, one of the early choices that have to be made has to do with the nature of "time". Is time discrete or dense? Is it represented by the natural numbers, by the non-negative rationals, by the non-negative reals or by some other structure?

In order to achieve a higher degree of generality, in the technical report

A. Jeffrey, S. Schneider, and F.W. Vaandrager. A comparison of additivity axioms in timed transition systems. Report CS-R9366, CWI, Amsterdam, 1993

the authors proposed to consider an algebraic definition of time domain. Since I like that definition, and I have it used it myself in a couple of papers, allow me to use this post to publicize it.

Define a monoid (X,+, 0) to be:

• left-cancellative iff (x + y = x + z) implies (y = z), and
• anti-symmetric iff (x + y = 0) implies (x = y = 0).
  

We define a partial order on X as x <= y iff x+z = y for some z in X. A time domain is a left-cancellative anti-symmetric monoid (D,+, 0) such that <= is a total order. Note that one can define a nation of subtraction over a time domain in the obvious way: if x <= y then y-x is the unique z such that x+z=y.

All of the structures mentioned above are, of course, time domains, but so is the set {0}. A time domain is non-trivial if D contains at least two elements. Note that every non-trivial time domain does not have a largest element, and is therefore infinite. Note moreover that + is not required to be commutative, so, for instance, suitable sets of ordinals with ordinal addition form a time domain.

I often find it worthwhile to work with time domains specified with the above degree of generality, and to use properties of specific "concrete" time domains only when they are really needed to obtain certain results. However, maybe this is the axiomatic devil in me talking :-)

Why hasn't the above definition become more popular in the literature on timed process algebras?

Gödel Prize 2007

The Gödel prize 2007, co-sponsored by EATCS and ACM SIGACT, is awarded to Alexander A. Razborov and Steven Rudich for their paper "Natural Proofs", Journal of Computer and System Sciences, Vol. 55, No. 1, 1997, pp. 24-35. (The conference version of the paper was first presented at the Twenty-sixth Annual ACM Symposium on Theory of computing, Montreal, Quebec, Canada. 1994, pp. 204 - 213.)

For discussions of the importance of this result in computational complexity, see here, and here. (Two posts from two of my favourite blogs.) Wikipedia has an entry on natural proofs.

Congratulations to Alexander A. Razborov and Steven Rudich, two outstanding members of the TCS community, for the award.

Addendum: The citation for the award is available here.

Iceland as an International Workplace in Science

Today, I participated in the workshop "Ísland sem alþjóðlegur vinnumarkaður vísindanna" ("Iceland as an international workplace in science") organized by Rannis, the Icelandic fund for research. At the workshop I delivered a presentation entitled How Do you Like Iceland? A View from a Foreign Academic. In case anybody is interested, the slides for my talk are available here. As you can see, I tried to give the Icelandic attendees a cathartic experience and some food for thought.

The latter part of this interesting workshop was attended by a few politicians. I am happy to report that all of them went on record as saying that the amount of funding available for science in Iceland should be increased substantially. Hopefully, these words will turn into deeds after the elections

This event also saw the signing of the European Charter of Researchers by the rectors of the Icelandic universities. Funnily enough, I had already been present at the signing of the same document by the rectors of the Italian universities in Camerino in July 2005. (Italy was the first country to sign the document.)

Robert H. Sloan on Being an NSF Program Director

Via the Geomblog, a blog that I warmly recommend, I learned about this two-page article by Robert H. Sloan, who was program director for the “Theory of Computing program” at NSF from January 2001 till August 2002. This is a light-hearted piece on why one should serve the community in that role, and what it takes to do a good job at it.

Here is a quote I liked:

Being a program director also gives you the ability to provide two good services to your research community. First, you have some ability to drive the direction of the research community. Second, you get to run the best, fairest competitions for funding possible. There is really quite a difference between the best panel run by somebody who knows the research area, knows who are likely to be good panelists, and is good at managing such things, and a panel run by an outsider who is a fair to middling manager of such things.

Indeed there is, but somehow we all hope that it is somebody else who takes care of running the best and fairest for funding possible.

The Geomblog offers another quote from the piece on the hazardous job of being Dean of Undergraduate Studies.

On the topic of community service, my stint as head of department is going to end in a couple of weeks or so. My department and the School of Science and Engineering have undergone a sudden restructuring, and we have hired Ari K. Jónsson (NASA Ames) to become Dean of the new School of Computer Science. I'll write more on all of the above when the dust settles, and I find some breathing space.