Accepted Papers for CONCUR 2007

The list of accepted papers for CONCUR 2007 is finally out. You can browse through the list here. The programme looks exciting, and I am looking forward to attending the conference.

The list of invited talks and tutorials is here. It will be a great honour to deliver an invited talk at that conference. (An honour that I cannot help but feel should have been bestowed on many other colleagues of mine.) I will eventually post the slides for my talk on this blog. Check this space if, for some reason, you are interested in the talk I plan to give.

What is a Free Name in a Process Algebra?

This is the question addressed by a short paper by Flemming Nielson, Hanne Riis Nielson and Henrik Pilegaard that appears in Information Processing Letters 103 (2007), pp. 188-194. In the paper, the authors show that the standard definition of free name is not preserved under the structural congruence, which is one of the sanity properties one would expect to have.

The traditional definition of the set of free names of a process term stipulates that the set of free names of a parameterized constant A(x₁,...,x_n) is {x₁,...,x_n}. Moreover, a term of the form A(y₁,...,y_n) is structurally congruent to P[y₁,...y_n/x₁,...,x_n] if the body of A(x₁,...,x_n) is the term P.

Consider now, for instance, the constant A(x) with body 0. The A(x) has x as its only free name. But this term is structurally congruent to 0, whose set of free names is empty! This is an example showing that the traditional definition of free names is not preserved by structural congruence, and we certainly want a process constant to be congruent to its body.

Why didn't anybody notice this before? As the authors write in their paper "Unfortunately the notion of free names is usually considered so simple that a formal definition is dispensed with and this occasionally shows up as problems in proofs."

In that paper, the authors develop a fixed point approach to the set of free names, argue that the set of free names can be computed efficiently and show that it is invariant under structural congruence.

I strongly recommend reading the paper.

Book Promotion

I apologize for the self-promotion and marketing :-)

In case any of you are looking for some summer reading, I recommend, not surprisingly, the book advertised in this flyer. If you purchase the book using the flyer, you'll have a 20% discount. Get your university library to order a few copies!

Here is what the endorsers of the book have to say about it. (Edited excerpts from the endorsements appear on the back cover for the book.)

ICALP 2008: Call for Workshops and Web Site

The call for workshops for ICALP 2008 has been posted on a large collection of mailing lists today. Consider proposing a workshop and making a trip to Iceland for the event! The deadline for workshop proposals is October 31, 2007. You'll be notified of acceptance/rejection of your proposals by 21 November 2007 at the latest.

The web site for the conference is located here. It is still preliminary, but all of the pieces of information that are relevant at this stage are already in place. For a sneak preview of the call for papers, look here.

Watch this space for further information on the development of the conference organization.

Avi Wigderson's Louis Clark Vanuxem Lectures

I recently stumbled across the slides for "A world view through the computational lens", three talks given at Princeton University by Avi Wigderson. These talks, which were delivered in the Louis Clark Vanuxem series, form an excellent companion to the talk that Papadimitriou recently gave at FCRC. See this post.

The plan for Wigderson's series of lectures is as follows.

• Lecture I: "Algorithms: a common language for nature, man and computer ." [PowerPoint]
  
• Lecture II: "Time, space and the cosmology of computational problems." [PowerPoint]
• Lecture III: "Cryptography: secrets and lies, knowledge and trust." [PowerPoint]

There is a lot of inspiration to be drawn from those slides. Is TCS really the "new math"? Only time will tell, but this really a good refrain to listen to anyway :-)

Computing Community Consortium Workshop at FCRC

The Computing Community Consortium (CCC) was recently created by the Computing Research Association (CRA) and is funded under a cooperative agreement from the National Science Foundation (NSF). The purpose of the CCC is to catalyze the computing research community to debate longer range, more audacious research challenges; to build consensus around research visions; to articulate those research visions; to evolve the most promising visions toward clearly defined initiatives; and to work with funding organizations to move the challenges and visions toward funding initiatives.

This week the CCC is organizing a workshop at the 2007 Federated Computing Research Conference. The slides for the contributed talks given so far are available here. (Lazowska's slides are still missing at the time of writing since his talk will be delivered today. I am looking forward to seeing them!) They are all interesting at first sight. In particular, I want to encourage readers of this blog to look at the wonderful slides for Christos Papadimitriou's talk on the Algorithmic Lens. The slides give Christos Papadimitriou's view of the impact that computer science is having on other sciences, and can offer all of us plenty of food for thought as well as material for enticing students to CS.

In case you do not have time to look at the slides, the executive summary of the talk, presented on the last slide reads:

• The algorithmic world view is changing the sciences: mathematical, natural, life, social
• CS is placing itself at the center of the scientific discourse and exchange of ideas
• And this is only the beginning…
  

Thanks Christos!

Addendum: Ed Lazowska's slides are now on line.

Rejecting Excellent Papers

Is it good for a journal, no matter how prestigious, to reject excellent scientific contributions on the grounds that it gets substantially more first-rate submissions than it is able to accept? In TCS, I am aware that JACM has such a policy, and I wonder whether it is backfiring badly. (My, possibly wrong, impression is that several authors decide not to submit top-notch papers to that journal because of that policy. I myself have always some trouble in deciding whether a paper is among the best papers of the year in its area since this seems to involve some crystal-ball gazing.)

A recent, remarkable instance of this kind of rejection is mentioned in a letter in the latest issue of the Notices of the AMS. (See here, on page 2 of the file. The letter is co-signed by Vaughan Pratt, one of my favourite theoretical computer scientists.) Apparently, the editorial board of the Journal of the AMS, which is the flagship journal of the American Math Society, has declined to publish a 14-page paper reporting on Friedrich Wehrung's solution to Dilworth's Congruence Lattice Problem for its lack of “interaction with other areas of mathematics”. The problem had been open for about fifty years, and drove the development of lattice theory during that time. See this web page for more information.

I am sure that the author will rapidly publish the paper in a top-notch journal, given that it had glowing referee reports. What I am not sure of is how many, apparently superb papers, a journal can decline to publish before authors stop submitting to it.

I guess that, as usual, the great judge will be Time.

Addendum 12 June 2007: A look at Friedrich Wehrung's publications page indicates that the aforementioned paper of his is going to appear in Advances in Mathematics.

June/July Notices of the AMS

The latest installment of the Notices of the AMS is out with a new look and some interesting-looking articles. I am certainly going to look at the article on The Mathematical Work of Jon Kleinberg by Gert-Martin Greuel, John Hopcroft, Margaret H. Wright, and at the contribution on the highly-successful math department at UCLA. The contribution by Graetzer on Two Problems That Shaped a Century of Lattice Theory looks worth a browse, even though the math is surely way beyond my knowledge of lattice theory.

Enjoy.

Invited Speakers at ICALP 2008

This is my second news item on the organization of ICALP 2008 (7-11 July 2008, Reykjavik, Iceland). On behalf of the organizing committee, I am pleased to give you the preliminary list of confirmed invited speakers. These are:

• Ran Canetti (IBM T.J. Watson Research Center and MIT, USA),
• Bruno Courcelle (Labri, Universitè Bordeaux, France),
• Javier Esparza (Technische Universität München, Germany),
  
• Muthu Muthukrishnan (Google, USA) and
  
• Peter Winkler (Dartmouth, USA).

In addition, the recipients of the EATCS award and of the Gödel prize 2008 will deliver talks.

Anna, Magnus and I are very glad to be able to offer participants at ICALP 2008 this outstanding set of invited talks.

Preliminary call for workshops and call for papers will be posted on this blog and on mailing lists very soon. Watch this space if you want to be the first to know!

AITO Dahl-Nygaard Prize Winners for 2007

I just saw that the Dahl-Nygaard Prizes for 2007 will be given to Luca Cardelli, Microsoft Research Cambridge (Senior prize) for his overall contribution to both theory and practice for object-oriented languages, and to Jonathan Aldrich, Carnegie Mellon University Pittsburgh (Junior prize) for his recent contribution to expressing and verifying software architecture in object-oriented languages.

I am very pleased to see Luca Cardelli honoured in this way, and I trust that this won't be the last award he will receive for his outstanding research achievements. Luca is a one-man research team, and he is equally at ease in theoretical as well as in implementation work. The text accompanying the notification singles out his famous book "A Theory of Objects", published with Martin Abadi in 1996, the Ambient Calculus (developed with Andy Gordon) and his work in Computational Systems Biology.

Congratulations to Luca!

Ranking

My gmail RSS monitor has alerted me that the June issue of CACM includes the article Automatic and versatile publications ranking for research institutions and scholars by Jie Ren and Richard N. Taylor. In that article, the authors briefly discuss the role of rankings of institutions and individuals in modern academic life, present the main criteria used in existing rankings, and introduce their own fully automatic ranking system, which is available here.

I have not played with the authors' system yet, but the tables they present to substantiate its quality make for some interesting reading. The top five computer science departments in the US, according to their ranking, are as follows.

1. MIT
2. University of Maryland, College Park
3. CMU
4. Georgia Institute of Technology
5. Stanford

UC Berkeley is "only" 10th (something that I find surprising), Princeton is 22nd and Harvard is 41st (which I find less surprising).

In Software Engineering, as an Italian abroad I am glad to see the Politecnico di Milano in 8th place and the University of Bologna in 41st. Amongst individual researchers in SE, Paola Inverardi is ranked 17th. Perhaps interestingly, the SE rankings given in the article differ significantly from those obtained by others in a previous ranking exercise.

This is what the authors have to say.

Our ranking is significantly different from the JSS ranking. The second column in Table 2 shows that only two of the top 15 institutions from the JSS ranking are among the top 15 of our ranking. The second column in Table 3 shows that only two of the top 15 scholars from the JSS ranking are among the top 15 of our ranking.

Two policy disparities probably contribute to the difference. First, we included two conferences in our ranking that the JSS ranking did not consider. Secondly, our ranking and the JSS ranking selected different journals and these journals contributed scores differently. The JSS ranking heavily relies on papers published in itself and the journal Information and Software Technology. It also includes a magazine, IEEE Software. The JSS ranking receives almost no influence from ACM Transactions on Software Engineering and Methodology. This study illustrates that the framework can produce dramatically different results when used with different policies, even for the same field.

What does this indicate? Automatic rankings will be very useful in the future, but it will be all the more important to specify clearly how such rankings are obtained. In particular, when evaluating the results of such ranking exercises, I'd really like to know what publication outlets were considered, what weight they were given, and what weight was given to multi-authored papers. I do not see why the author of a multi-authored paper should necessarily receive a fraction of the points awarded to the paper. Is writing a paper with a co-author less work than doing it alone?

Invited Paper for CONCUR 2007

I have posted my contribution to the Proceedings of CONCUR 2007. The paper, coauthored with Anna and entitled The Saga of the Axiomatization of Parallel Composition, is a survey of recent work Anna and I have done in collaboration with Wan Fokkink, Bas Luttik and MohammadReza Mousavi. We published some of this work directly in journals, and so it felt appropriate to present it in a conference proceedings. I'll be basing my invited talk at CONCUR on the paper.

Thanks a lot to Anna, Bas, Mohammad and Wan for our pleasant collaborations so far. I hope to do some justice to our joint work in Lisbon. It'll be a bit of a challenge to make the audience interested in the story I have to tell, but it is one I hope to meet decently well. It'll be up to the participants at CONCUR 2007 to tell whether I'll succeed.

Surprisingly, the list of accepted papers for the conference is not yet available from the CONCUR 2007 web site. I am looking forward to viewing the programme for this event.

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.