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.

Bourbaki

Lance Fortnow recently devoted a post to The Bourbaki Lecture. Reading his post, reminded me that I had in mind of scribbling a couple of lines on the book Bourbaki: A Secret Society of Mathematicians by Maurice Mashaal, Pour la Science - AMS, 2006, 168 pp. I came across that book while looking for another one at the university library, and decided to borrow it. I am glad I did!

For one, I did not know that André Weil (1906-1998) introduced the symbol for the empty set that we now universally use. (A whole issue of the Notices of the AMS is devoted to Weil.) Nor did I know that Boubarki coined the terms injection, surjection and bijection, and invented the notion of filter. Not to mention the striking similarity between André Weil and Eugenio Moggi! (Eugenio, I hope that you don't mind me mentioning this!)

More seriously, I really enjoyed reading that book, and I warmly recommend it. It tells what was good, and what was bad, with Bourbaki and its view of mathematics. It is also full of eminently quotable sentences from the Bourbaki members. Examples?

"You can't do good work in applied mathematics until you can do good work in pure mathematics." (Jean Dieudonné (1906-1992), cited on p. 119)

"[...] logic is the mathematician's hygiene, but it does not provide his meals. The big problems constitute the daily bread on which he lives." (André Weil in The Future of Mathematics, 1948) Shame on you Weil!

The closing paragraph of the book is poignant:

"Despite some mistakes, Bourbaki did add a little to the "honour of the human spirit." In an era when sports and money are such great idols of civilization, this is no small virtue."

Indeed, not to mention that the members of Bourbaki have included some of the greatest mathematical minds of the last century.

Great minds can also make great mistakes (for instance, Bourbaki's disdain of probability theory had a very negative effect on French work in that very important area of mathematics, and Bourbaki was very dogmatic in his view of mathematics), and one of the virtues of the book is that these are not swept under the carpet. Read it, and form your own opinion on this non-existent, and most prolific mathematician.

Change of Dean

At a meeting with the staff members of the School of Science and Engineering held yesterday, the new rector, Svafa Grönfeld, announced that the dean of the school, Bjarki Brynjarsson, is stepping down from his position.

A five-person evaluation committee will be formed by early next month, and its first assignment will be to set down criteria for the selection of the new dean for the School. I expect that an advertisement for the position will be published in early March.

Watch this space if you are interested in the job!

Trying to Influence Research Funding in Iceland

Parliamentary elections are coming up in Iceland, and a bunch of scientists are trying to put funding for research on the political agenda. This group blog is an attempt at keeping the discussion of this issue alive. As you can see, most of the posts are encrypted in Icelandic. However, since my knowledge of Icelandic is not what it should be, I use English for my posts on that blog.

In case anybody is interested, I posted an entry entitled More Funding and More Variety! In that post I sing the praise of some types of funding that is available in countries like The Netherlands and Denmark, but not in Iceland. Comments are most welcome.

Too Many People Have Way Too Much Money

Icelandic business is thriving, and Icelandic businessmen are buying companies, football teams, supermarket chains etc. all over the place. There is a new breed of very wealthy people out here, who are not particularly bothered by the fact that, e.g., food is 65% more expensive than the European average here.

I just heard that the director of Samskip, one of the local new rich man, has just turned 50. For his birthday, he had Elton John sing for his guests. Cost: over 100 million ISK (about 1,110,789 euros)! This is one sixth of the annual budget of the Icelandic research council. I estimate that, with that money, I could hire at least 11 visiting professors for a year, changing the face of my department.

Life is not fair.

Lack of Funding for Italian Researchers Logic

Not so long ago, I reported with pleasure on a success story for Italian research in logic. Unfortunately, it looks like it is now time for bad news regarding research in logic in Italy.

Over the last few days, I have been reading a sequence of messages posted on the mailing list of the Italian Association for Logic and its Applications (AILA) related to the results of the applications for PRIN projects. (I think that PRIN is an Italian acronym standing for "Projects of National Interest".) The list of PRIN projects funded in the subject area of mathematics and computer science is here. A quick browse through the list gives me the impression that not enough of the funded projects are from computer science. Moreover, the only funded project related to logic in computer science is

OMODEO Eugenio

Università degli Studi di TRIESTE

22.680

Sviluppo su grande scala di dimostrazioni certificate

(Large scale development of certified proofs. Amount: 22.680 euros.)

One can also make the case that the project

DEGANO Pierpaolo

Università degli Studi di PISA

94.500

Sistemi e calcoli di ispirazione biologica e loro applicazioni -- BISCA

impacts on logic in computer science, broadly construed. (By the way, well done Pierpaolo!)

Funding for projects in mathematical logic and its relationships to computer science is conspicuously absent, despite the strength of Italian researchers in this area. Albeit the lack of funding will have very negative consequences on logic research in Italy, this is not the only thing that is bothering Italian logicians. From what I gather, all of the projects proposals from logicians received the same one-line evaluation, namely interesting, but marginal, as well as the same numerical score.

I do not know who the reviewers of the projects were, and I know nothing about the quality of the submitted projects. However, I feel that I have to take a firm and public stance against this uniform, general and vague "scientific" evaluation for 50-page long proposals. Would any of us be happy to write a long paper and have it rejected with a one-liner? And can logic research be at all labelled as being marginal?

Logic is the calculus of computer science! Apart from its intrinsic scientific and cultural interest, this fact alone shows that logic research is by no means marginal. In fact, thanks to its close connections with computer science, logic is the most applied branch of mathematics! (This is not just the opinion of your truly. I invite Italian readers --- assuming they exist, of course :-) --- to check out pages 108-109 of the interview with Enrico Giusti in the excellent book Professione Matematico. Note that Giusti is not a logician.)

I hope that the Italian mathematical community does not consider logic a marginal subject, and that, in the future, the evaluation of project proposals will involve expert reviewers from abroad, as it is done essentially everywhere else. This will be a great step forward towards the use of proper peer review in the distribution of the funding available for scientific research, and will increase the transparency of the whole process.

A Flurry of Prizes in Maths

It is prize time in the mathematical world. The Wolf Foundation has announced that Harry Furstenberg (Hebrew University of Jerusalem) and Stephen Smale (University of California, Berkeley) will share the US$100,000 2006-7 Wolf Prize in Mathematics.

The AMS has instead awarded its prizes for 2007. Once more the AMS-MAA-SIAM Morgan Prize for Outstanding Research by an Undergraduate Student went to an MIT student, Daniel Kane. It is humbling experience to see that this BSc student has already about 16 papers under his belt :-(

The February 2007 issue of the Notices is out. It features an interview with Lennart Carleson coauthored by my former Aalborg colleague Martin Raussen, and a beautiful book review Symmetry and the Monster: One of the Greatest Quests of Mathematics--A Book Review by Robert Griess. I liked it so much that I could not resist buying the book today. I might report on the book when I read it.