Programming the Universe

I recently finished reading the book Programming the Universe by Seth Lloyd, Professor of Mechanical Engineering at MIT. The book is a very pleasant, thought-provoking read, and its message is honey to the ears of us computer scientists. To see why, it suffices only to read the first few lines in Chapter 1 of the book.

This book is the story of the universe and the bit. The universe is the biggest thing there is and the bit is the smallest possible chunk of information. The universe is made of bits. Every molecule, atom, and elementary particle registers bits of information. Every interaction between those pieces of the universe processes that information by altering those bits. That is, the universe computes, and because the universe is governed by the laws of quantum mechanics, it computes in an intrinsically quantum-mechanical fashion; its bits are quantum bits. The history of the universe is, in effect, a huge and ongoing quantum computation. The universe is a quantum computer.

Basically, Seth Lloyd's message is that information is just as important as classic physical quantities like energy in understanding the universe, and that viewing the universe as a quantum computer can actually help us understand it better. He even proposes a theory of quantum gravity based on this view---a theory that, unlike others, may even be testable experimentally.

You might like to have a look at a scientist's cut from the material Lloyd penned down for the book here. There you will also find some interesting quotes from referee reports Lloyd received for some of his papers, and the following estimate on the number of operations performed by the universe since the big bang.

The universe can have performed 10¹²⁰ ops on 10⁹⁰ bits (10¹²⁰ bits including gravitational degrees of freedom).

I wonder if Scott Aaronson has reviewed this book on his blog. It would be interesting to hear his opinion.

Vardi on Process Equivalences

Last Saturday, Moshe Vardi posted the paper Branching vs. Linear Time: Semantical Perspective (invited ATVA'07 paper with Sumit Nain). This is a nicely written and balanced paper distilling Moshe's thoughts on the choice of semantics for concurrent processes. I have no doubt that it will generate some healthy discussion in the concurrency theory community. I strongly encourage my two readers to have a look at it.

Oversimplifying the message in the paper by Moshe and Sumit, in their opinion the plethora of process semantics is due to "semantic underspecification". To overcome this underspecification, they propose to develop process semantics based on the following principles.

1. Principle of Contextual Equivalence: Two processes are equivalent if they behave the
   same in all contexts, which are processes with “holes”.
2. Principle of Comprehensive Modeling: A process description should model all relevant
   aspects of process behaviour.
3. Principle of Observable I/O: The observable behaviour of a tested process is precisely
   its input/output behaviour.

In the paper, Moshe and Sumit apply their approach to transducers, and show that, once the aforementioned three principles are applied, there is a trace-based equivalence that is adequate and fully abstract.

As the authors state in the paper "In conclusion, this paper puts forward an, admittedly provocative, thesis, which is that process-equivalence theory allowed itself to wander in the “wilderness” for lack of accepted guiding principles. The obvious definition of contextual equivalence was not scrupulously adhered to, and the underspecificity of the formalisms proposed led to too many interpretations of equivalence.While one may not realistic expect a single paper to overwrite about 30 years of research, a more modest hope would be for a renewed discussion on the basic principles of process-equivalence theory."

What do you think?

Rivest Wins Marconi Prize

MIT's Department of Electrical Engineering and Computer Science continues its rich harvest of awards. My RSS feeds monitor has informed me that Ron Rivest has been awarded the Marconi prize. See here for the MIT news item. Rivest has been named the 2007 Marconi Fellow and prize-winner for his pioneering work in the field of cryptography, computer and network security.

The Parking Algorithm

Furio Honsell is one of Italy's best known theoretical computer scientists. His research covers many areas within volume B TCS, and he was one of the proposers of the ‘Anti-Foundation Axiom’ for non-well-founded set theory. Furio was the first computer scientist to become rector of an Italian university, Università di Udine to be precise, and is now serving his second mandate as rector.

Unlike most of us, Furio is also known to the general Italian public for his participation in the TV show Che tempo che fa, where he discusses topics related to computer science and mathematics in a way that makes them accessible to a general audience. My mother, for instance, is fascinated by his witty and very clear discussions of topics that normally would not be aired on a TV show.

What has this all to do with "The Parking Algorithm"? A few days ago, walking back to my deck chair after a swim in the Adriatic sea, I saw a man read a volume by Furio entitled "L'Algoritmo del Parcheggio" ("The Parking Algorithm"), published by Mondadori, which is a major Italian publishing house. I was amazed. I stopped and asked this man whether I could write down the bibliographic details for the book, which I simply had to buy!

Furio is definitely doing a lot for promoting an appreciation for computer science and mathematics amongst the general educated public in Italy, and he must be doing it right if people read his book on the beach! I know that this is one of my, possibly boring, mantras, but we badly need more people who, like him, are not afraid to devote some of their time to writing books and articles for the general public, and who have the charisma to appear on TV and captivate viewers like my mother or that man who ended up buying his book and reading it under the sun-shade. (I also admire his time-management skills. Being a rector does not leave him a lot of time for research or book writing.)

For the record, I did buy Furio's book, but I'll have to wait for my mother to finish reading it before having a close look at it. I'll review Furio's book at some point in the future, but don't hold your breath.

"Reactive Systems" Is Out: Buy Your Copy Now!

A few days ago, I checked the web page at Amazon.co.uk for my latest book Reactive Systems: Modelling, Specification and Verification, which I have already shamelessly advertised in previous postings. I was surprised to read that only four copies were left in stock (and only one is in stock right now, so hurry!), especially because the official publication date for the book is 9 August 2007.

My copy of the book landed in my mailbox yesterday, as partial compensation for the departure of the hard disk in my laptop, the only computer I own :-( It was quite an experience to browse through the results of a few years of work while wondering whether I really had any part in writing the text filling those pages. This is how I often feel whenever I look at some work of mine. Was it really I who contributed to write/do that work? Something to ponder while waiting for a new hard disk, even though I know that it was really a different person from the one typing these characters who did it.

Anyway, I hope some of you will like the book, whoever wrote it.

Edsger W. Dijkstra Prize for 2007

The winner of the Edsger W. Dijkstra Prize for 2007 is the paper "Consensus in the presence of partial synchrony'' by Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer, which appeared in the Journal of the ACM, Vol. 35, No. 2, April, 1988. pages 288--323. (A preliminary version appeared in PODC 1984.) This is the second time that Nancy Lynch winds up this prize since she had received it before in 2001 for her classic paper

Michael J. Fischer , Nancy A. Lynch and Michael S. Paterson. "Impossibility of Distributed Consensus with One Faulty Process", Journal of the ACM, April 1985, 32(2):374-382.

One can say that, despite how faulty researchers may be in evaluating the quality of scientific work, there is definite consensus on Nancy's huge impact on research in the principles of distributed computing! Congratulations to the winners.

It is sad that Larry Stockmeyer is not here with us to enjoy yet another achievement in his distinguished career. He passed away in 2004. Look here for some commemorations that took place at that time.

Special Issue of JLAP Devoted to FOSSACS 2006

This to let you know that a special issue of JLAP devoted to selected papers from FOSSACS 2006 is now available on line. Anna and I edited the issue. I hope that you'll enjoy reading the papers in that volume.

Many thanks to all the colleagues who contributed to the success of the conference, and to the expert referees who devoted some of their time to a careful evaluation of the submitted papers. It has been a pleasure to work with all of you.

Software from Reykjavík University Wins the 2007 GGP Competition

These are good days for AI (and CS) research at Reykjavík University, and I trust that you'll forgive me for self-promoting the achievements of my department. The finals of the 2007 General Game-Playing competition at the AAAI conference have been won by "our" own CADIAPlayer, developed by Yngvi Björnsson and his MSc student Hilmar Finsson within CADIA, our centre for AI research. (As you can see, Yngvi is very hot these days!) The aim of the GGP competitions is to help develop systems that can accept a formal description of an arbitrary game and, without further human interaction, can play the game effectively.

According to Yngvi, the competition was very exciting, especially the final, which was played against ClunePlayer from the University of California, Los Angeles. (ClunePlayer was the second place finisher last year, and the world-champion from two years ago).

Congratulations to Hilmar and Yngvi for a great success!

Checker is a Draw

I am very happy to see that the news of the week in Science reports on a triumph of AI and (theoretical) computer science. A team from the games group at the University of Alberta, Canada, has announced that checkers is now solved: perfect play by both sides leads to a draw. Determining the outcome of the game brings AI search techniques to bear at a totally new level of complexity. The game of checkers has roughly 500 billion billion possible positions (5 x 10²⁰)! These are state spaces of "model-checking size" :-)

Unfortunately, the full text of the Science article is only available to subscribers. The abstract is here. See also the web page of Chinook, the world checkers champion.

I am also very happy to report that one of the members of the team that solved checkers, Yngvi Björnsson, is a colleague of mine at Reykjavík University. This success will bring some media exposure for our department. (I know that process algebra cannot be expected to do so, alas :-))

Addendum: Bill Gasarch also has a, more detailed, post on this piece of news. Do read the comments to his post, which are, as usual, interesting.

Corrado Priami on Italian Prime Time TV

Last Thursday I ended up watching part of SuperQuark, a well-done science programme that has been running on Italian TV (RAI 1 to be precise) for some time now. To my pleasant surprise, the programme had a feature on the Centre for Computational and Systems Biology---a joint undertaking between the University of Trento and Microsoft Research. (You can watch the video, in Italian, here.)

The feature included excerpts of an interview with Corrado Priami, the president of the centre, and Luca Cardelli made some visual guest appearances.

It was a great pleasure to see a centre involving computer science in a crucial way make an appearance on prime-time TV. I can only compliment Corrado for having achieved so much in his career so far. I still remember sharing some work-space with him at the HP research lab in Pisa in late 1991-early 1992. He was fresh from his MSc degree then, and working on very different things.

Showcasing the impact of computer science on other sciences on prime-time TV can only be good for our field. Who is going to be next?

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.

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.

Accepted Papers for CALCO 2007

The list of accepted papers for CALCO 2007 is now available here. There are a few papers in that list of potential interest to concurrency theorists.

Meanwhile, the by now fairly typical discussion on the role of FOCS/STOC in TCS is raging on the complexity weblog. You will probably enjoy reading it. As usual, I find the idea that STOC and FOCS represent all theoretical computer science difficult to defend. Mind you, FOCS and STOC are great conferences, but many areas of TCS are not represented in recent editions of those conferences.

When did volume B research stopped being represented at those conferences? When I have a little time on my hands, I might try to investigate this question. I'd appreciate hearing the opinion of whoever is out there.

Paul Graham's Take on Judgements

Paul Graham has several interesting essays on his web pages. I just read a recent one entitled Two Kinds of Judgement. This short essay deals with the types of judgement we usually face in our daily lives and lots of what Graham writes applies to our scientific careers too. The gist of his message is that there are two different ways people judge you. The first, and rarer, type of judgement arises when people are really interested in judging you correctly. The correctness of the decision is important in this type of judgement and this means that we usually have some form of appeal system against a decision we perceive to be incorrect. We usually encounter this type of judgement when we submit a paper to journal, say.

A second much more common type of judgement does not have the goal of judging you correctly. As Graham writes:

It's not aimed at producing a correct estimate of any given individual, but at selecting a reasonably optimal set.

We meet this type of judgement whenever we submit a paper to a conference or workshop. Of course, we all feel that our work is worthy of selection when we submit it. (Indeed, as they say in Naples, "Even a cockroach is beautiful for its mum".) That is why we are usually not so good at accepting that our papers are not selected for presentation at an event. Here Graham's following words from his essay may be worth keeping in mind:

Our early training and our self-centeredness combine to make us believe that every judgement of us is about us. In fact most aren't. This is a rare case where being less self-centered will make people more confident. Once you realize how little most people judging you care about judging you accurately—once you realize that because of the normal distribution of most applicant pools, it matters least to judge accurately in precisely the cases where judgement has the most effect—you won't take rejection so personally.

And curiously enough, taking rejection less personally may help you to get rejected less often. If you think someone judging you will work hard to judge you correctly, you can afford to be passive. But the more you realize that most judgements are greatly influenced by random, extraneous factors—that most people judging you are more like a fickle novel buyer than a wise and perceptive magistrate—the more you realize you can do things to influence the outcome.

Indeed, we could all try to write better papers that sell our ideas---once we have them, that is. As Paul Halmos famously wrote in his automathography:

"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?"

Anyway, Paul Graham's essays are well worth reading while sharpening one's pencils. (Have you heard the scraping sound of my pencil sharpener for some time now?) Check out also his recent essay on the death of Microsoft. You might also enjoy looking at the web page for his new venture firm, Y combinator. Cool name, isn't it?

Mathematicians Map E8

Just a line towards the end of a long degree accreditation day. (I am optimistically assuming that our degrees will be accredited :-))

This is by now old news, but I liked reading this report on the work that mathematicians in the Atlas project did to map the inner workings of one of the most complicated structures ever studied: the object known as the exceptional Lie group E₈. Reading sentences like:

"The most important thing that we've done is written an algorithm which converts some very difficult abstract mathematics, the representation theory of real groups, into combinatorics which can be computed. This is a substantial accomplishment."

and

"In the process of taking these known mathematical results, and converting them into a computer program, we have deepened our understanding of the mathematics."

should be like honey to the ears of us computer scientists.

E₈ in the news gives pointers to news coverage on the work that the people in the Atlas project did.

It is now time to join the discussion with our evaluation committee.

Nancy Lynch is Awarded Knuth Prize

The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) has awarded its 2007 Knuth Prize to Nancy Lynch of the Massachusetts Institute of Technology (MIT) for her influential contributions to the theory of distributed systems. Further information on the award is available here. Nancy Lynch is the first woman to receive this award since its inception in 1996.

The award of the Knuth Prize to Nancy is a great advertisement for the areas of distributed computing, and modelling, verification and validation of computing systems. Congratulations to Nancy! I look forward to seeing more awards to outstanding women in computer science.

Computing Degrees and Careers Information from the ACM

Following up on my previous post, I just saw that the ACM has made available a new brochure to prepare High School students for careers in computing: http://computingcareers.acm.org. The brochure describes the major areas of study available in the field, as well as a wide range of career
opportunities. Of note is also the information on the web site, including Frequently Asked Questions and Top 10 Reasons to Major in Computing.

I will be using this material in my efforts to attract Icelandic students to computer science. I must freely admit that, with all due respect to civil engineering, I find it very difficult to understand why students choose that field of studies in large numbers, and do not even consider computer science. As my Latin ancestors would have said, "De gustibus non disputandum est" ("There is no arguing about tastes").

Concurrency on Ars Mathematica

The latest post on Ars Mathematica, a very interesting math blog, features concurrency theory! The post mentions a position paper by Samson Abramsky published in the ENTCS volume Essays on Algebraic Process Calculi, which I coedited with Andy Gordon.

It is good to see mathematicians referring to concurrency theory, even if just on their blogs and for a quote from André Weil :-)

Enticing Students to Learn CS

It is that time of the year again. Applications are open, and we eagerly monitor the number of students that have elected to apply for one of the degree courses we offer (two year Diploma in Applied Computing, BSc in CS, BSc in Software Engineering, and MSc in CS). The department of CS at Reykjavík University is by far the best in the country, and one of the very best in all areas of science. (I must freely admit that there are only three CS departments in Iceland, so being the best might not mean much after all :-)) There are plenty of well-paid, exciting jobs available out there for CS graduates, and our graduates have many job offers to choose from. Computing is the heart of modern life and society, and offers an unmatched breadth of engaging problems to work on, and the potential for lifelong learning. As Jeannette Wing puts it in her piece on computational thinking, "to reading, writing, and arithmetic, we should add computational thinking to every child’s analytical ability."

Based on these (for us obvious) premises, one would expect student enrollments in our CS degrees to be increasingly high. Unfortunately, as of today, the figures paint a totally different, and utterly inexplicable and depressing, story. The number of applications is at an all-time low, and we are considering many plans to try and stop the rot. At the same time, enrollment in several engineering degrees is increasing. Even female students are now considering engineering as a viable subject to study. Instead, CS does not seem to cross their mind at all.

Could this have to do with the totally wrong equation "computer science = programming"? And what about the stereotype that a computer scientist is an autistic, male, sun-avoiding, coke-drinking nerd who programs and fixes computers all day? I have no answers to these questions. These days I am putting on my travelling salesman clothes, and give (hopefully energetic) talks on the beauty and importance of CS to a few high-school students who bother to show up. Whether this will have any effect I do not know. What I do believe is that it is time to send out the powerful message that computer science is the science of the 21st century Renaissance man. No other science today touches on so many others, and on society as well. What we need are more people like David Harel and Jeannette Wing who have the courage to explain CS and its basic ideas to the rest of society, including our fellow scientists---many of whom just consider computing as a useful technology.

Let's pick up the gauntlet, and put pen to paper.

Some Results on BPA with Interrupt

In case anyone is interested, I recently posted on my recent papers page a study of the equational theory of BPA with the interrupt operator. (See Luca Aceto, Silvio Capobianco and Anna Ingolfsdottir. On the Existence of a Finite Base for Complete Trace Equivalence over BPA with Interrupt. ) This is the same language Anna and I studied in a very pleasant collaboration with Wan Fokkink and Sumit Nain that eventually led to a TCS publication. In that paper we showed that, modulo bisimilarity, there is no finite collection of sound equations that can prove all of the valid closed equations. This holds true even in the presence of a single action.

In the present paper we show that, unlike bisimilarity, complete trace equivalence affords a finite, ground-complete axiomatization, provided that the set of actions is finite. Moreover, we show that, when the set of actions is a singleton, the interrupt operator is a derived BPA-operator, and that complete trace equivalence affords a finite complete axiomatization over BPA with interrupt.

In the presence of at least two distinct actions, we isolate a collection of valid equations. A proof of their (in)completeness has so far escaped us. Feel free to get in touch with me if you have any idea on how to prove this!

The Equational Theory of Timed CCS

A couple of weeks ago, I posted a paper on my recent publications page presenting some negative results on the equational theory of Wang Yi's Timed CCS (TCCS) modulo timed bisimilarity. The paper, Impossibility Results for the Equational Theory of Timed CCS, is coauthored with Anna Ingolfsdottir and MohammadReza Mousavi. (So my Mousavi number is now 1.)

The aim of the paper is to revisit the study of the equational theory of parallel composition in TCCS by obtaining results in the spirit of those that Faron Moller showed for Milner's CCS. We prove that timed bisimilarity is not finitely based over TCCS. Moreover, unlike in the setting of CCS, adding two "natural" variations on the (timed) left-merge operator to TCCS does not yield a finitely axiomatizable theory.

In passing, we sharpen the so-called Gap Theorem of J.-C. Godskesen and Kim G. Larsen by showing that it holds also in the setting when the set of actions is a singleton. Unlike the proof of the original result by those authors, which goes via a translation to timed automata, ours is entirely process algebraic.

Thanks to Anna and Mohammad for a pleasant, instructive and humbling collaboration. I, for one, am always overawed by the fragility of these results. One has to be very careful in making sure that the technical details work. An apparently innocuous change in the semantics of the operators can make a huge difference in their properties, and thus in the validity of the statements one is trying to prove. Our ICE-TCS seminar speaker yesterday, Freyja Hreinsdóttir, quoted a mathematician as referring to a conjecture as being "obviously true, but unproven". I am afraid that I do not trust those statements. For what it is worth, my "obviously true, but unproven" conjectures turn out to be false more often than not :-(.

Ready to Preorder

Ready to Preorder: Get Your BCCSP Axiomatization for Free! is the Amazon.com-sounding title of a recent paper by Wan Fokkink, Anna Ingolfsdottir and yours truly. This paper had a nine-month gestation period. We began working on it when Wan paid a visit to Iceland for a week in late May-early June 2006 to deliver a talk at our second ICE-TCS Theory Day, but the paper was only completed in February 2007.

In the paper we offer an algorithm for turning an axiomatization for a behavioural preorder in the linear time-branching time spectrum that includes the ready simulation preorder into an axiomatization for the kernel of the preorder. The algorithm preserves finiteness, ground-completeness and omega-completeness of the axiomatization that it receives as input. The proof of its correctness relies on an analysis of the so-called cover equations for the semantics in the spectrum we study in the paper.

I thoroughly enjoyed working on that paper. The development of the technical details in that work reminded me yet again of a few valuable lessons that I tend to forget when I feel that I am short of time and that I badly need to produce some research output to keep my conscience at bay.

1. It is easy to make mistakes in proofs unless one is very careful in checking even the seemingly most obvious of claims. (This is what happens to me at least.)
2. Haste is never a good advisor.
   
3. When I feel that a paper is done, I should let it rest for a day, and proof read it once more.
   

I feel that I need this self-advice more than ever :-) Reading Terence Tao's General Advice on Submissions is a reminder of what I should be doing. I hope that I do not fall way too short of the Platonic ideals Tao sets forth.

Thanks again to Anna and Wan, the coauthors with whom I have written the largest number of papers, for another very instructive and pleasant collaborations. I hope that there will be another one in the near future.

Tom Henzinger Named ACM Fellow 2006

You probably all know that the 2006 Turing Award will go a woman for the first time ever. The award goes to Frances E. Allen (Fellow Emerita at IBM) for contributions that fundamentally improved the performance of computer programs in solving problems, and accelerated the use of high performance computing. See here for further details. (I strongly suggest that you also have a look at the ongoing discussion on this award, and other previous ones, going on here. The discussion indicates once more how parochial we can all be at times, and that several researchers out there still think of TCS as only covering volume A research.)

What might be less known, however, is that Tom Henzinger was named amongst the ACM Fellows for 2006. Tom is selected for contributions to formal verification and hybrid systems. Tom's ACM fellowship is very good for the fields of computer-aided verification, concurrency theory and TCS at large.

Congratulations Tom!

Two Posts on Martin Kruskal

Bill Gasarch and Clyde Kruskal, guest blogging for Lance Fortnow, have posted two entries (here and here) on the late Martin Kruskal. Both posts are definitely worth reading, but I especially enjoyed the latter. I just thought that some of you might like reading it too.

By the way, Joseph Kruskal of minimun spanning tree fame is Martin Kruskal's brother. (Historically, the first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka (see Boruvka's algorithm).)

Tao on "Good Mathematics"

Early this week, Terence Tao posted an essay entitled What is Good Mathematics? on the arXiv. I thoroughly enjoyed reading this beautifully written article, commissioned to the author by the Bulletin of the AMS. Even though the description of the technical developments in the story of Szemeredi's theorem (see also here), which Tao uses as an example of good mathematics, passed me by (not surprisingly, alas), there is so much warmth and thoughtfulness in that essay to serve as an example of essay writing to all of us.

The final lines of the piece will serve as an appetizer.

Thus I believe that good mathematics is more than simply the process of solving problems, building theories, and making arguments shorter, stronger, clearer, more elegant, or more rigorous, though these are of course all admirable goals; while achieving all of these tasks (and debating which ones should have higher priority within any given field), we should also be aware of any possible larger context that one’s results could be placed in, as this may well lead to the greatest long-term benefit for the result, for the field, and for mathematics as a whole.

Well said indeed!

EATCS Award 2007

Breaking news. The EATCS award 2007 will go to Dana Scott (CMU). The official motivation for the award is appended. I nominated somebody else, but there is no arguing about an award to the father of the denotational semantics of programming languages :-)

Dana Scott has also received the following prizes:

LeRoy P. Steele Prize	American Mathematical Society, 1972
Turing Award (with Michael Rabin)	Association for Computing Machinery, 1976
Harold Pender Award	University of Pennsylvania, 1990
Rolf Schock Prize in Logic and Philosophy	Royal Swedish Academy of Sciences, 1997
Bolzano Medal for Merit in the Mathematical Sciences	Czech Academy of Sciences, 2001

See here for some biographical information.

===========================

EATCS AWARD 2007
MOTIVATION

Dana Scott is an outstanding scientist with a deep and lasting influence on Theoretical Computer Science. In a few words his contributions belong to three tracks of fundamental research:

- The introduction, in collaboration with Rabin, of non-deterministic machines in Automata Theory, which earned them the 1976 ACM Turing Award.

- The mathematical foundation to the denotational semantics of programming languages, also known as the Scott-Strachey approach to semantics, for which he is best known in Theoretical Computer Science.

- The invention of LCF (Logic for Computable Functions), which was hugely influential in the development of program logics and modern proof checking technology.

More recently he has further advanced the foundations of denotational semantics in two directions: Synthetic Domain Theory (a way to view domains as sets in a non-standard set theory) and Equilogical Spaces, which appear to be a natural extension of domains.

In 1930-40 the work of mathematicians such as Goedel, Turing, Tarski, and Church had profound consequences on Mathematical Logic and gave origin to Computability Theory. Dana Scott is among the top researchers who carried that mathematical tradition into Computer Science. Denotational semantics is the natural evolution of Tarskian (compositional) semantics for logical languages into the realm of programming languages, and Domain Theory provides the needed semantic objects. In particular, effectively-given domains (and Information Systems) extend the notion of computability well beyond natural numbers and strings.

LCF was a major contribution to program logics, which led to work on PCF, sequentiality, higher-type computability, and modern proof checking technology.

Dana Scott has obtained fundamental results also in Set Theory, Model Theory, Modal Logic, Topology, Category Theory, and Realizability. His work on constructive mathematics, and also his lucid expositions of the work of others, had a great influence on the uses non-classical logics (e.g. constructive reasoning, modal logics for concurrency, propositions-as-types) in computing. He made a whole generation see the potential of non-standard logics, an idea as revolutionary as the one of non-standard geometries had been.

Dana Scott's research career has spanned Computer Science, Mathematics, Logic, and Philosophy, and has been characterized by a concern for elucidating fundamental concepts, with a focus on mathematically hard problems that bear on these concepts. His influence in forming
mathematical foundations for Computer Science is now visible over a period of over 40 years. The European research community of Theoretical Computer Science owes a lot to his thoughts and is flourishing while pursuing the directions he started.

Brain Drain and Brain Gain, Redux

I have received the following comments on my brain drain post from Jorge A. Perez, a Colombian student who just started his PhD studies at the University of Bologna under the supervision of Davide Sangiorgi, one of the Italian TCS researchers who made it back home safely. I am happy to post Jorge's comments, as they indicate that Italian CS is moving in the right direction.

I've read your recent post with interest, as I make part of the minority that has chosen Italy as a place to do a PhD. I am a Colombian, and have recently joined the CS department at Bologna,
under a new scheme for admitting (and reserving scholarships) for foreigner students.

Two specific comments on the post:

- It is certainly surprising to observe that Italy and Colombia share this "runaway brains" problem. This, of course, occurs because of very different reasons. Naturally, the surprise behind all this is that Italy is a G8 country and Colombia is a third-world country that spends most of its money on military expenses.

- Recently, there has been an increasing offer of PhD positions in CS for foreigners. Indeed, a number of CS departments (e.g., Bologna, Pisa, Verona, Trento) now admit foreign applications, usually based on CV and recommendation letters. This seems to be the right direction in order to compete with other European countries. Moreover, this initiative could be imitated in several other fields.

I have to say that even with the problems Italy has in some aspects of doing research, at Colombia Italy is seen as a very attractive option to do a PhD in CS. The possibility of working with strong researchers is an incredible advantage that, in several ways, compensates some
things that could be considered as drawbacks.

Brain Drain and Brain Gain

Nature has a short article that tries to explain the context for the "Brain Gain" plan of the Italian Ministry for University and Research, including some recent developments related to abuses of the ministerial plan. There are also online comments. (These are substantially fewer than I would have expected for such a contentious topic.) I invite all of you to read the piece, and Luca Trevisan's excellent post on the The Runaway Brains phenomenon.

I do not have that much to add to Luca T.'s analysis, so I'll just limit myself to adding a couple of comments, and to reiterating some opinions and facts that I already stated in some related posts.

First, let me go on record once more as stating clearly that there is a lot of talent in Italian universities. Italian researchers perform very well despite the lack of support the system gives them. However, Italy must do its very best to attract outstanding, foreign scientists (and students) in order to compensate for its brain drain. (I hate this expression, but it has become so widely used that I am forced to use it too.) This won't happen unless much needed, expensive, and probably very unpopular structural changes are made.

Every CS department in virtually every university that matters in the world has foreign members of staff and foreign students (at least at MSc and PhD level). A look at an average Italian department paints a different picture. According to the interesting little book Ipotesi sull'università by the mathematicians Mariano Giaquinta and Angelo Guerraggio only 2% of the students in Italian universities are foreigners. Moreover, for good or for worse, an observer is not unlikely to notice a certain amount of academic inbreeding in the lineage of members of staff.

Something is badly wrong when a school of the outstanding quality of the Scuola Normale Superiore di Pisa has 11 PhD scholarships in mathematics, receives only 13 applications (all from Italian candidates, and none from the school itself), and selects only 4. (Source: Una storia inquietante (An unresting story) by Mariano Giaquinta and Angelo Guerraggio in Lettera Matematica Pristem 60, pp. 4-6.) Does this mean that even a school of that quality does not advertise its vacancies internationally? Or, possibly even worse, does this mean that no student out there perceives that school in Italy as a good location for PhD education? The lack of local applicants might be read as indicating that Italian students with an MSc in mathematics from the Scuola Normale Superiore di Pisa prefer to work on their PhDs somewhere else, and most likely abroad. This is great, but history shows that not many of those people will make the trip back to Italy to bring back to my home country the experience they have amassed abroad.

One of the online comments to the Nature news item reads:

Usually Italian scientists working in Italy are the best one.
In fact, an Italian scientist will not go abroad for a Ph.D. or postdoc
if she/he can remain in Italy with a good salary.
This is due to the fact that Italy is a wonderful place to live.

So, it is true that in Italy there are very few research positions
but they are usually occupied by the best ones.

Italy is indeed a lovely place to live. However, data like the aforementioned ones seems to indicate that it is not quite correct to say an Italian scientist won't go abroad if (s)he can remain in Italy. A look at at the list of people I compiled off the top of my head while writing this post indicates otherwise. The writer of that comment might ask himself why foreign researchers do not consider Italy as an attractive working place despite being a lovely place to live. The answer won't be pretty.

As an Italian abroad, I sincerely hope that things will change soon.

Advertisement for Deanship

As promised in a previous post, here is the "call for dean" just issued by the School of Science and Engineering at Reykjavík University. I am curious to see what applicants we'll get. (Note: I am not a member of the evaluation committee :-))

Corrigendum 4/2/2007: The deadline for applications is 1 March 2007, and not 15 February 2007, as incorrectly stated in the above announcement.

New Chair for the Etaps Steering Committee

Breaking news: Vladimiro Sassone has just been elected as the chair of the ETAPS steering committee. Congratulations to Vladimiro, and thanks to Perdita Stevens, the outgoing chair, for her sterling work.