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!

## Friday, February 23, 2007

## Wednesday, February 21, 2007

### 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).)

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).)

## Saturday, February 17, 2007

### 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.

Well said indeed!

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!

## Wednesday, February 14, 2007

### 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:

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.

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.

## Tuesday, February 13, 2007

### 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.

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.

## Sunday, February 11, 2007

### 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:

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

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.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.

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.

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

## Friday, February 02, 2007

### 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.

## Thursday, February 01, 2007

### 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.

Subscribe to:
Posts (Atom)