Wednesday, May 28, 2008

CONCUR 2008: Accepted Papers

The list of accepted papers for CONCUR 2008 is now available here. There will be plenty of reading to do once the ICALP organization and the course I am delivering now are over.

On a separate, but ICALP-related, note, the winner of the 2008 Gödel Prize is the paper Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time by Daniel A. Spielman and Shang-Hua Teng, Journal of the ACM (JACM), 51(3), May 2004, 385-463. The results in the paper were first presented at the Annual ACM Symposium on the Theory of Computing (STOC 01), 2001, pp. 296-305.

The prize will be awarded at the conference during the award ceremony held on Thursday, 10 July. Both Daniel A. Spielman and Shang-Hua Teng will attend the ceremony.


Tuesday, May 27, 2008

Change of Editor for the BEATCS

The June issue of the BEATCS will be the last issue with Vladimiro Sassone as editor of the Bulletin. Maria Jose Serna will take over from Vladimiro, who will assist her for the next couple of issues.

Vladimiro has been in charge of the Bulletin for the last five years. He has streamlined the production process and made it web-friendly. (The whole Bulletin is now produced using pdflatex.) He has inaugurated two new columns, designed and implemented a new editorial style, and was a prime mover on the issue of open access for the BEATCS.

I like to think that the quality of the BEATCS has continued improving during Vladimiro's editorship, and the whole TCS community owes him a lot of gratitude for the enormous amount of energy he has put in the editorship of the BEATCS.

I wish Maria the best of luck for her new and important role. The BEATCS needs a strong editor, and it won't be easy to follow Vladimiro's footsteps and to improve on his work. Let's help Maria by contributing pieces to the BEATCS and by thinking about ways to make that publication even better. If you have any ideas, please post a comment. I will do my best to mention your suggestions during the EATCS council meeting at ICALP 2008.

Saturday, May 24, 2008

The Swan Song of SEN2 at CWI

This is a guest post from MohammadReza Mousavi on an event held yesterday at CWI to "celebrate" the demise of the project SEN2 at CWI. This marks the end of an era at CWI, and for the concurrency community all over the world. My own research career and interests over the years have benefited from, and have been strongly influenced by, the work being carried out within SEN2 and collaborations with several researchers who have been affiliated with it. Thanks to Mahammad for this post reminding all the concurrency-theory community how important SEN2 has been for the field.

Yesterday at CWI, there was a celebration of (the funeral service for) 25 years of concurrency theory, practiced at SEN2.

The meeting was attended by some 100 participants. All SEN2 leaders and all its graduated Ph.D. students were present. Four distinguished speakers gave four very interesting talks. What comes next is a brief summary of what I can recall from these interesting presentations. An abstract of the talks can be found here.

  • Jos Baeten gave a brief history of 25 years of concurrency theory and practice at CWI. It all started with Jan Bergstra who cooperated with John Tucker (then at Leiden) and went on with the leadership of Jan Willem Klop, Jos Baeten, Frits Vaandrager, Jan Friso Groote, Wan Fokkink and Jaco van de Pol, all of whom after a short while became full professor at universities around the Netherlands. SEN2 has produced: about 1000 PAM talks (the last to begin given on June 18, 2008 by Jan Willem Klop), about 10 research projects, 25 Ph.D. thesis (2 in progress), hundreds of articles and CONCUR conferences (of which till now, 18 conference are held), which is a truly impressive track record.
  • Then, Gerard Holzmann gave a wonderful talk on the history and state of the art on Model Checking (with an emphasis on Spin). He divided the history of model checking into 4 development phases: formalisms (from 1978-1988), algorithms (from 1988-1998), veracity (from 1998-2008) and multi-core model-checking (I am not sure if I recall this one well, from 2008-2018).
  • The third speaker was Jan Bergstra, who is the father of concurrency theory in the Netherlands. (Mathematics Genealogy project counts about 50 pupils of his, see here.) He gave a very intriguing talk about many foundational issues for algebraic specification and process algebras. He said that he always believed in a number of dogmas including: superiority of total functions over partial functions, and also superiority of projective limit models to those induced by structural operational semantics. He made his point by defining a theory of meadows, which defines division as a total function (with 1/0 = 0). He showed that a very sensible algebraic theory can then be developed for meadows. Jan Bergstra stated (and to some extent showed) that this can simplify the foundations of mathematics even at the level taught in primary and high schools. His talk touched upon many other fundamental issues such as suitability of Turing Machines as the (only) foundational model for computability.
  • Finally, Moshe Vardi presented a nice overview of the development of temporal logics for industrial applications. He gave an overview on expressiveness and verification complexity for linear and branching temporal logics and the developments led to practical versions of such logics such as PSL and SVA (SystemVerilog Assertion). He concluded that SEN2 has not only produced a lot of fish, but trained many skilled fishermen for the Dutch TCS community and the latter is the main contribution of SEN2, which will last forever.
Let me conclude, on a personal note, by saying that, as usual, Moshe has expressed in a nutshell one of the main forms of impact, if not the main one, that any academic institution worth its salt should have: the development of highly skilled academics who will continue sowing the seeds for the future development of their science both nationally and abroad. I won't mention names, but it will be clear to any observer that SEN2 has played this role very well over its life span.

Monday, May 19, 2008

More on Reverse Age Discrimination in Italian Universities

A while back, I wrote a post spurred by a reading of the commentary Reverse Age Discrimination, written for Nature Physics by Francesco Sylos Labini and Stefano Zapperi, two physicists based in Rome. I was reminded of that piece over the week-end, when I glanced at this on-line article from La Repubblica, a widely read Italian newspaper. The article is in Italian, and so won't be accessible to most readers. However, the figures mentioned in that article will be clear to everyone.

Here is the executive summary. Italian academic staff has never been older. The average age of associate and full professors is over 51. Over 50% of Italy's full professors is older than 60, about 8% is over 70, only 1,7% is under 40 and less than 19% is under 50. About 25% of the associate professors is over 60, and only 10% is under 40. Looking at researchers, a paltry 2% is younger than 30.

How does my home country compare with other European countries? Not well, alas, judging from the figures mentioned in that article. The average age of university professors is 45 in France, 44 in Spain and 42 in Germany. There is more. In Italy only 4% of university professors is below 34. Compare this figure to the ones in France (21%), the UK (27%), Finland (28%) and Germany (32%), and you will see why Italy continues to suffer from brain drain whereas other European countries are reversing this trend.

Can anybody point out similar statistics for countries like Australia, Canada, Israel and the USA, say? And what about Eastern Europe?

One thing seems clear to me, and it breaks my heart to say so. A country that does not offer better job opportunities to its young academics will suffer in the not-so-distant future and runs the risk of losing whole generations of gifted researchers. I hope that things will change soon, but I am not very optimistic.

Wednesday, May 14, 2008

Concurrency Column for the BEATCS: June 2008

I have just posted the Concurrency Column for the June 2008 issue of the BEATCS. It is an excellent survey paper entitled 20 Years of Modal and Mixed Specifications by Adam Antonik, Michael Huth, Kim G. Larsen, Ulrik Nyman and Andrzej Wasowski.

Modal transition systems are a variation on the classic model of transition systems where transitions come in two flavours: those that any refinement of the given specification must possess, and those that it may, but is not required to,
have. This model of computation was introduced about twenty years ago by Kim Guldstrand Larsen and Bent Thomsen. Since then, it has been the subject of investigation by several groups of researchers, and interest in this model and in its sibling that goes by the name of mixed specifications has grown over the last few years. In the light of the recent rapid growth in the research literature on modal and mixed specifications, and their applications, I thought that it was appropriate to devote an instalment of the Concurrency Column to a survey of recent results and open problems in the field. I am very happy to be in a position to offer the readers of the Concurrency Column this excellent overview paper by some of the prime movers in the development of the theory and applications of modal and mixed specifications. I trust that this piece will be of general interest, and I hope that it will entice several researchers to contribute to the on-going work on these models. Enjoy!

If you'd like to contribute a piece to the Concurrency Column, do write to me.

Sunday, May 04, 2008

Interview to an Opinionated Mathematician

About a fortnight ago, I had to make a sudden trip and, as reading material, brought with me some print-outs that had been lying on my desk for a long time. One of those was An Interview with Vladimir Arnold, which appeared in the Notices of the AMS in 1997. Vladimir Arnold is regarded as one of the great living mathematicians and the number of disciplines in which he has worked is truly astounding. (The areas are Dynamical Systems, Differential Equations, Hydrodynamics, Magnetohydrodynamics, Classical and Celestial Mechanics, Geometry, Topology, Algebraic Geometry, Symplectic Geometry, and Singularity Theory.) What I found out by reading the above-mentioned interview is that he is certainly a man with strong opinions and that he has no qualms about airing them.

One answer of his that really got me thinking was this one:

Lui: Do you notice any differences in the way people from different cultures do mathematics?

Arnold: I was unaware of these differences for many years, but they do exist. A few years ago,
I was participating in an International Science Foundation (ISF) meeting in Washington, DC.
This organization distributes grants to Russian scientists. One American participant suggested
support for some Russian mathematician because “he is working in a good American style.”
I was puzzled and asked for an explanation. “Well,” the American answered, “it means that he is traveling a lot to present all his latest results at all our conferences and is personally known to all experts in the field.” My opinion is that ISF should better support those who are working in the good Russian style, which is to sit at home working hard to prove fundamental theorems which will remain the cornerstones of mathematics forever!

It is certainly true that travel and networking are fundamental parts of our daily life at work. What Arnold seems to be saying, however, is that we may be pushing this part of our work too far, and that this might be detrimental to the purely scientific part of our work. Of course, each of us has different work pattern, but there seems to be a tendency these days to shun good old scholarship for the modern gods of networking, leadership and what not.

Arnold also paints a picture of his days as a student at Mechmat (Moscow State University Mechanics and Mathematics Faculty) in the fifties. He says:

"The constellation of great mathematicians in the same department when I was studying at the
Mechmat was really exceptional, and I have never seen anything like it at any other place. Kolmogorov, Gelfand, Petrovskii, Pontriagin, P. Novikov, Markov, Gelfond, Lusternik, Khinchin,
and P. S. Alexandrov were teaching students like Manin, Sinai, S. Novikov, V. M. Alexeev, Anosov, A. A. Kirillov, and me."

I guess that it is hard to argue against his opinion. I looked up some of these names on the web, and this is really a most impressive collection.

Finally, to add a little more to the debate, Arnold seems to indicate that in 1997 it was still possible for a Western mathematician to build a good career rediscovering weaker versions of results known earlier to Russian mathematicians. And I have not mentioned his opinions on Bourbaki and the French mathematical establishment :-)

There are definitely worse ways to spend a few minutes during a flight than reading that interview.

ICALP 2008 Early Registration Deadline TOMORROW

The early registration deadline for ICALP 2008 is tomorrow. I strongly encourage you to register by May 5 at the latest to take advantage of the early registration rate and secure suitable accommodation.

In the meantime, the list of accepted papers/speakers for the affiliated workshops are being made available. See