Monday, April 28, 2008

Call for Nominations: The 2008 Edsger W. Dijkstra Prize in Distributed Computing

The call for nominations for the 2008 Edsger W. Dijkstra Prize in Distributed Computing is now out. See here. The prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade, and is sponsored jointly by the ACM Symposium on Principles of Distributed Computing (PODC) and the EATCS Symposium on Distributed Computing (DISC). The award is presented annually, with the presentation taking place alternately at ACM PODC and EATCS DISC - this year it will be presented at PODC 2008.

Let's think up outstanding nominations!

Monday, April 21, 2008

Complete Scientific Programme for ICALP 2008

The scientific programme for ICALP 2008 is now available here. It looks like we are going to have a scientific feast, and hopefully many of you will come and join us.

Wednesday, April 16, 2008

ICALP 2008: Bird's Eye Programme

In case you are wondering what is going to happen at ICALP 2008, and when, I encourage you to look at the skeleton of the conference programme, which is available here. Some more detail is presently available for track B.

The conference organizers strongly recommend that you register for the ICALP conference and book accommodation before May 5th, as that date is the deadline for registering at the lower fee. After May 5th hotel rooms will also start to get released since July is the prime holiday season in Iceland and the demand for hotel accommodation is very high.

NOTE:
For those who have not decided yet which workshop(s) they are going to attend when registering for the conference, it is possible to register for workshops at the lower fee until June 5th by sending an e-mail to the Conference Secretariat.

Saturday, April 12, 2008

Look Who's Doping

The inimitable Dr. Z wrote in his April 1, 2008, opinion:

But I strongly disagree with the unfortunate decision to forbid the use of any result, or solve any open problem posed by, the great Paul Erdös, on the grounds that he was "doping" by using stimulants like amphetamines. While I definitely do not recommend anyone to start taking prescription drugs, mathematics is not (yet) the tour-de-France, and if we start forbidding them, what's next? coffee?. It is no coincidence that Erdös quipped that a mathematician is a machine that turns coffee into theorems. Without coffee (and unfortunately other stimulants) we would not have progressed beyond Euclid. Coffee is so much part of our culture that it would take much more than one committee to disallow it at AMS meetings.
On the same day, a press release written by evolutionary biologist Jonathan Eisen of the University of California, Davis, declared that the US National Institutes of Health is to crack down on scientists 'brain doping' with performance-enhancing drugs such as Provigil and Ritalin.

These were, of course, intended as two funny pranks. Now, however, Nature is spotlighting a study on the use of cognition-enhancing drugs by academics. (Alas, a subscription is needed to access the text.) The article in Nature reports on the results of a survey conducted by that journal on whether readers of Nature (scientists) would consider “boosting their brain power” with drugs. The article states that 1,400 people from 60 countries responded to the online poll.

Apparently "one in five respondents said they had used drugs for non-medical reasons to stimulate their focus, concentration or memory." Moreover, use of drugs did not differ greatly across age-groups. According to the article, "the numbers suggest a significant amount of drug-taking among academics." So, not only academics drink more than rest of population on average (or so I seem to recall reading somewhere recently), but they also enhance their performance by taking drugs :-) Will we soon have to sign declarations that our work was not done under the influence of performance-enhancing drugs as well as copyright release forms? Or will we have to have drug tests taken when we submit papers to conferences or journals? And will all authors of an article have to take such tests?

On a more serious note, as a parent, I was a little concerned when I read that

When asked whether healthy children under the age of 16 should be restricted from taking these drugs, unsurprisingly, most respondents (86%) said that they should. But one-third of respondents said they would feel pressure to give cognition-enhancing drugs to their children if other children at school were taking them. Morein-Zamir found this coercive factor very interesting. “These numbers strongly suggest that even if policies restricted their use by kids, pressure would be high for parents,” she says.
(The emphasis is mine.) Would you give drugs to your children to enhance their mental performance?

Sometimes I wonder what our answer would be if we were offered a Faustian pact promising that we would solve, say, two fundamental problems of our choice at the price of our "soul". What would your reaction to this "two-for-the-price-of-one" offer be? Has any science-in-fiction novel ever been written on this theme?

Addendum: After I wrote this post, Luca Trevisan pointed out to me the delightful short story "The devil and Simon Flagg" by Arthur Porges. I recommend it!

Friday, April 11, 2008

Accepted Papers for ICALP 2008--Track C


The list of accepted papers for track C of ICALP 2008 is now available here. You can get an overview of all of the accepted papers from this web page.

I strongly encourage all of you who are planning to come to Iceland for ICALP 2008 to start planning your trips now. In addition, if you register now you can take advantage of the present strength of many foreign currencies vis-a-vis the Icelandic crown :-)

I also strongly recommend signing up for the conference dinner. The conference dinner will be held at Perlan (The Pearl). (See the photo above.) The Perlan restaurant is consistently one of the best restaurants in town and is Reykjavik's latest landmark. Towering over the city from one of its highest hills, Perlan sits atop the geothermal reservoir tanks overlooking the city. The top floor restaurant is enclosed in a glass dome and the floor rotates 360o degrees every 90-120 minutes. The restaurant offers a stunning panoramic view of Reykjavik and the surrounding areas.

See also the other events in the social programme. I'll post more information on ICALP 2008 on this blog at a later date. In particular, the Gödel prize winner for 2008 will be announced very soon.

Thursday, April 10, 2008

Terence Tao Receives NSF Award

The NSF has bestowed the Waterman Award to Terence Tao. (The press release is here.) The list of Tao's awards is already very long, and includes the Salem Prize in 2000, the Bochner Prize in 2002, the Fields Medal and SASTRA Ramanujan Prize in 2006, and the MacArthur Fellowship and Ostrowski Prize in 2007.

And he even finds the time to write very detailed and informative blog posts!

Wednesday, April 09, 2008

Accepted Papers for ICALP 2008, Track B

The list of accepted papers for track B of ICALP 2008 is now available. The list of accepted papers for ICALP Track A has been posted yesterday evening, and already a few blogs have pointed to it. See the Complexity Weblog, David Eppstein, and Michael Mitzenmacher. It seems to me that the PCs for the ICALP tracks have faced some very hard choices this year since the quality of the submissions was very high.

I'll post the list of accepted papers for track C when it becomes available.

Sunday, April 06, 2008

Rankings of CS Departments in the USA

I learned from Mihai Patrascu's blog that the US News rankings for 2008 have been released. The rankings for computer science, for CS theory, and for mathematics do not show any truly major surprises.

In your opinion, what are the best CS departments in theory outside the US? And how would you compare them with the top departments in the US News ranking? Perhaps more modestly, what are the best CS departments in TCS in your country?

Tuesday, April 01, 2008

The Equational Theory of Prebisimilarity over Basic CCS with Divergence

I recently posted the short paper

Luca Aceto, Silvio Capobianco, Anna Ingolfsdottir and Bas Luttik. The Equational Theory of Prebisimilarity over Basic CCS with Divergence. March 2008.

This paper studies the equational theory of prebisimilarity, a bisimulation-based preorder introduced by Hennessy and Milner in the early 1980s, over basic CCS with the divergent process Omega.

It is well known that prebisimilarity affords a finite ground-complete axiomatization over this language. This finite axiomatization is obtained by adding the inequation

Omega <= x

to the complete axiomatization of bisimilarity over basic CCS. In the above paper, we prove that this ground-complete axiomatization is also complete in the presence of an infinite set of actions. Moreover, in sharp contrast to this positive result, we show that prebisimilarity is not finitely based over basic CCS with the divergent process Omega when the set of actions is finite and non-empty.