N is a Number

Yesterday, ICE-TCS hosted its first movie event with the projection of the documentary film N is a Number: A Portrait of Paul Erdös by George Csicsery. I bought the DVD of this award winning documentary using my Springer author discount, and, rather than watching it at home, I decided to share it with my colleagues at Reykjavík University. I also hoped that some of our students would show up to watch the documentary. (Every opportunity is good to entice students to study TCS! Unfortunately, however, no student took the bait and joined us :-()

The documentary is good and I recommend it, even though it does not hold many surprises for people who have read the popular books on Paul Erdös. However, watching Paul Erdös strut his skills on the dias before diving into the mathematics was an enjoyable experience for somebody like me who never had the chance of seeing him "live".

I wonder whether he is still managing to keep the SF's score low wherever he may be now.

Addendum: The Erdös numbers of the members of ICE-TCS are here.

MohammadReza Mousavi in Reykjavík

Albeit belatedly, due to some last minute bureacratic hassles arising from the lack of experience of the staff at a young university like Reykjavík University, MohammadReza Mousavi has joined our little concurrency theory group at Reykjavík University. Anna and I are understandably thrilled at having him here. Mohammad will have a joint position between Reykavík University and TU Eindhoven.

The 'group' has doubled in size since August this year, with the arrival of Silvio Capobianco (a mathematician from Rome) and Mohammad. Their arrival has also strengthened ICE-TCS considerably, and their presence is giving Anna and me a good intellectual environment to work in. Now it's up to us to make the most of this opportunity, and I hope that we'll be able to capitalize on their scientific strength. If we don't, then it's going to be solely our fault.

The problems we encountered in getting a visa for Mohammad at the last minute seem to have some positive consequences. Together with the Icelandic research council, we are pressing the politicians here to establish a fast-track for researchers seeking visas and work permits to come and work in Iceland. Having a "researcher visa" procedure might make it more attractive for scientists to come and work here in the North Atlantic, at times when access to other countries is becoming more and more difficult. I'll keep you posted on the developments.

New Perspectives on Fairness

I have just posted the concurrency column for the October 2006 installement of the Bulletin of the EATCS. The October column is a lovely piece entitled New Perspectives on Fairness by Daniele Varacca and Hagen Voelzer.

Fairness is an important concept that appears repeatedly in various forms in different areas of computer science, and plays a crucial role in the semantics and verification of reactive systems. Entire books are devoted to the notion of fairness---see, for instance, the monograph by Nissim Francez published in 1986---, and researchers in our community have painstakingly developed a taxonomy of various fairness properties that appear in the literature, such as unconditional fairness, weak fairness, strong fairness, and so on. This research is definitely important in light of the plethora of notions of fairness that have been proposed and studied in the literature.

But when is a temporal property expressing a fairness requirement? The authors of this column have recently developed a very satisfying answer to this fundamental question by offering three equivalent characterizations of ``fairness properties'' in the setting of linear-time temporal logic: a language-theoretic, a topological, and a game-theoretic characterization. This survey discusses these recent results in a very accessible fashion, and provides also a beautiful link between the study of fairness and classic probability theory.

I trust that you will enjoy reading this piece by Daniele and Hagen as much as I did. It is not often that one sees notions and results from several areas of mathematics and computer science combine so well to offer a formalization of a concept that confirms our intuition about it.

MacArthur Genius Awards for 2006

Lance Fortnow has a post on the latest batch of "genius awards" by the Mac Arthur foundation. Awards in disciplines of potential interest to the readers of this blog are to

• Luis von Ahn.
  
• Terence Tao.
• Claire Tomlin. The announcement makes very interesting reading for a concurrency theorist, and for anyone interested in formal verification:
  

  Much of Tomlin's research concentrates on aeronautical applications of hybrid systems research, particularly aircraft flight control and air traffic conflict resolution. As the number of variables increases and their interactions become more complex, it becomes ever more difficult to guarantee that systems will always be within safe limits. Tomlin has developed practical algorithms for determining when unsafe conditions may arise, and for establishing feedback control laws for a hybrid system guaranteed to remain within a safe subset of all reachable states.
  

In keeping with my previous jazz-related post, I am glad to see that John Zorn, one of my favourite musicians and prime mover behind Tzadik Records, is one of the recipients of the award. Check out his Masada series if you have not done so already.

Congratulations to the winners of the awards!

Jazz meets Process Algebra

Bas Luttik's band, the Residence Jazz Sextet, now has a web site, and a CD. I heard a demo version of the CD, and it sounds good. On the band's web site, you can also listen to mp3 demos of the tracks on the CD. Enjoy it!

An Essay by Palamidessi and Valencia

Catuscia Palamidessi and Frank Valencia have written an essay on Languages for Concurrency, which will appear in the Programming Languages column of the Bulletin of the EATCS (edited by Ian Mackie (Kings College, London, UK) and David Sands (Göteborg, Sweden)). I enjoyed reading it myself---even though I hopefully knew the material it covers already---, and warmly recommend it.

This essay is a commendable example of `outreach activity´ from two very active members of the concurrency theory community. Let's give it to our students and colleagues from other areas of computer science to read, and let's try to sow the seeds of our research area in our departments. Something good is bound to come out of these kind of efforts. For the moment, thanks to Catuscia and Frank for offering a contribution in this direction.

New Award to Moshe Vardi

Moshe Vardi has been named as a co-recipient of the first LICS-test-of-time award for his paper An Automata-Theoretic Approach to Automatic Program Verification, co-authored with Pierre Wolper. Congratulations to Moshe and Pierre for yet another award!

See http://www2.informatik.hu-berlin.de/lics/#awards for a description of the award. I think that the idea to look back 20 years for the award is a good one, and look forward to seeing more awards in areas of logic related to concurrency theory and formal verification.

Experimental Blog for the IFIP WG on Concurrency Theory

Together with Wan Fokkink and Anna Ingolfsdottir, I recently set up a separate blog on concurrency theory. The aim of that blog is to serve as a dicussion forum for topics of interest to the members of IFIP WG1.8. I hope that the readers of this blog, if there are any, will contribute to the discussion threads that will be posted on the new blog.

PC Chair for FOSSACS 2008

FYI, the PC chair for FOSSACS 2008 will be Roberto Amadio. Sharpen your pencils and prepare good papers for that conference!

Gordon Plotkin is 60

On 7-8 September, LFCS, School of Informatics, University of Edinburgh, will host a symposium to celebrate Gordon Plotkin's 60th birthday. The detailed programme for that event lists a series of stellar speakers, and the list of participants is truly impressive.

This is really good to see. Gordon is one of the veritable giants in TCS, and he has had outstanding students and collaborators over the years. His contributions to the study of the semantics of programming languages (be it denotational, logical or operational) and to its mathematical underpinnings are well known, so I'll just limit myself to wishing Gordon a happy symposium.

What Are the Most Important Open Problems in Concurrency?

Let us assume that one can assess the healthiness of a research field, say concurrency theory, by looking at the most important open problems in that field. These open problems can be used to try and convince researchers in another area and students that the field of concurrency theory is "alive and kicking", and maybe entice a few of them to work within the field.

Based upon this thought experiment, wouldn't it be a good thing to have a repository of open problems that identify the present state of development in concurrency theory, and suggest directions for further research?

At some point in the past, I started putting together a list of open problems, but I have not really maintained it for a while. Will you help me revive this enterprise by sending me, or posting as a comment to this blog entry, a description of your favourite open problems in concurrency theory, together with links to partial solutions and pointers to the literature? This input of yours might even form the basis for a useful installment of the Concurrency Column in the Bulletin of the EATCS, and generate a lot of research in our field following what Luca Trevisan has called in this very informative blog entry the "Hungarian approach to mathematics": pose very difficult problems, and let deep results, connections between different areas of math, and applications, come out as byproducts of the search for a solution.

By the way, Luca Trevisan has a few very interesting posts related to Szemeredi's theorem and other results in additive combinatorics. (See this one, and the five blog entries on Szemeredi's theorem.) Those posts give an inkling of the level of mathematical sophistication that has been reached in TCS research from the volume A camp. Check them out!

A New Yorker Article on the Poincaré Conjecture

Yesterday I finished reading a rather long, but interesting article published in the New Yorker. The article, written by Sylvia Nasar (of Beautiful Mind fame) and David Gruber, describes some of the developments surrounding the proof of the Poincaré conjecture, has excerpts of an interview with Perelman, and offers us a glimpse of what happens behind the scenes of the mathematical arena. The former Fields medal winner and top-notch mathematician Shing-Tung Yau appears as the "villain" in the story.

I do not know if the content of the article is truly trustworthy, but it makes for some interesting, and at times arresting, reading. This excerpt, for one, tells the remarkable story of the recent publication of what could be a key paper in the story of the solution of the Poincaré conjecture:

On April 13th of this year, the thirty-one mathematicians on the editorial board of the Asian Journal of Mathematics received a brief e-mail from Yau and the journal’s co-editor informing them that they had three days to comment on a paper by Xi-Ping Zhu and Huai-Dong Cao titled “The Hamilton-Perelman Theory of Ricci Flow: The Poincaré and Geometrization Conjectures,” which Yau planned to publish in the journal. The e-mail did not include a copy of the paper, reports from referees, or an abstract. At least one board member asked to see the paper but was told that it was not available. On April 16th, Cao received a message from Yau telling him that the paper had been accepted by the A.J.M., and an abstract was posted on the journal’s Web site.

Quite a remarkable refereeing process for a paper proving one of the Millennium Problems of the Clay mathematical institute!

Italian TCS Presence at the ICM 2006

Today was a good day for Italian TCS at the International Congress of Mathematicians 2006. The inaugural talk in the section on Mathematical Aspects of Computer Science was delivered by Luca Trevisan (UC Berkeley). Luca's talk was based on the paper Pseudorandomness and Combinatorial Constructions.

Congratulations to Luca for being invited to deliver a talk at ICM 2006.

Question: How many Italian computer scientists have been invited speakers at the section on Mathematical Aspects of CS at the ICM so far?

I do not know the answer myself. Does any of my readers do?

Live Transmission from ICM 2006

The web pages for ICM 2006 point to this link for live trasmission of the sessions and recordings of previous sessions. Warning: I have not tried to view anything myself yet, so I hope this works :-)

One of yesterday's highlights for my family and close environment was Richard Stanley's invited plenary talk. Stanley is the "godfather of algebraic combinatorics", or so says Doron Zeilberger on his links page, and the former supervisor of Bridget Tenner (Kári's girlfriend) , and of Einar Steingrimsson, the head of the algebraic combinatorics research group at Reykjavik University.

For those of you who would like to read it, Stanley's paper for ICM 2006 is Increasing and decreasing subsequences and their variants (34 pages).

Fields and Nevanlinna Prizes

This is old news by now, but, in case you have not seen it already, at the opening ceremony of the 2006 International Congress of Mathematicians (ICM), four Fields Medals were awarded. The medalists are Andrei Okounkov, Grigory Perelman, Terence Tao, and Wendelin Werner. Perelman has apparently declined the award. At a press conference, John Ball (president of the IMU) said that Perelman will be recorded as having been awarded a Fields Medal but as having declined to accept it. Jon Kleinberg received the Nevanlinna Prize, and Kiyoshi Itô, who is 91, received the first-ever Gauss Prize. Congratulations to Jon, who also got a Mac Arthur fellowship in 2005. An AMS press release has more details about the six winners.

Luca Trevisan has "live commentary" from ICM 2006. Make sure you follow his lively blog reports! (For instance, look at his report on the laudationes for the prize winners.)

Today is a great day for TCS at ICM 2006. Avi Widgerson delivered his plenary talk "P, NP and mathematics: a computational complexity perspective", and brought one of the fundamental notions in Computer Science to the attention of a hord of mathematicians. I strongly advice all of you to read the beautiful paper he wrote for the occasion, and on which the talk is based. I look forward to reading Luca Trevisan's report on the talk.

Thanks Luca!

Addenda: BBC coverage, Guardian story, New York Times article.

I could not resist checking my distance from the 2006 Fields medal winners. According to the data on the AMS web site, my collaboration distance from all of the winners of the Fields medal is 6, apart from the one from W. Werner, which is 5. My Kleinberg distance is 4. Finally, my K. Ito number is infinite.

Scientifically speaking, my distance from each of these guys is infinite.

A Good Newpaper Article on Maths

Readers of this diary might enjoy looking at the article "Elusive Proof, Elusive Prover: A New Mathematical Mystery". This is an excellent example of coverage of mathematics in the press, and deals with the developments surrounding Perelman's proof of Poincaré’s conjecture.

This article is also very timely. The ICM 2006 kicks off tomorrow, and Richard Hamilton (Columbia University, New York, USA) will deliver a talk on the Poincaré conjecture at 17:15. As an Italian abroad, I am also proud to announce that Alfio Quarteroni (École Polytechnique Fédérale de Lausanne, Lausanne, Switzerland and Politecnico di Milano, Milan, Italy) will also deliver a plenary address tomorrow.

The section on Mathematical Aspects of Computer Science starts on August 26.

Colin Stirling in the Gödel Award Committee

I have heard from Mogens Nielsen that Colin Stirling has agreed to serve as one of the EATCS representatives in the Gödel award committee. This is great news for the concurrency theory community, and we should all be proud of Colin's nomination. (Colin is taking the place of P.L. Curien, whose term on the award committee ended this year, when he chaired the award committee.)

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computing Theory of the Association of Computing Machinery (ACM SIGACT). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and ACM Symposium on the Theory of Computing (STOC).

As I have already written in earlier posts devoted to this prize, a look at the list of winners clearly indicates a bias towards SIGACT-friendly research. During his presentation at ICALP 2006, Curien explained that this is a somewhat natural outcome of the fact that the prize is awarded by a committee formed by three SIGACT representatives and three EATCS members. Now, unlike SIGACT, the EATCS is an organization representing the whole of TCS, and its representatives in the Gödel award committee cover the areas of logic and semantics, automata and formal languages and algorithms and complexity theory. When it comes down to voting, papers in algorithms and complexity are more likely to get four votes than those in, say, logic and semantics.

Is this a desirable state of affairs? I am not so sure myself, but I believe that the EATCS should continue being involved in the Gödel prize. Let me wish Colin good luck with his work in the committee. I hope that we'll make his job easier by nominating excellent papers in logic and semantics for the award. After all, isn't it a bit weird that so few Gödel prizes are being given for work done in logic?

Handwritten Slides, Course Notes and Hard Copies of Old Papers

Anna and I had to make some drastic decisions when packing our things in Aalborg. Some of these decisions involved the material stored in the boxes stored in the university cellar that housed the contents of our offices there. We had between 15 and 20 boxes full of books, handwritten slides for talks and courses, hard copies of technical reports and papers, photocopies of (parts of) books and reprints of our papers.

Not having time to sort things, we eventually threw everything away, apart from a few books that we really cared about.

Was that a good decision to take? Well, for a start, we had been packing our things in the house for about a week, and we were sick and tired of it. Disposing of the reprints of our papers was not a painful decision at all since most of the papers are available electronically. However, when we told Kim G. Larsen that we had got rid of our handwritten slides, notes and course folders he immediately said: "That was a stupid thing to do! I still use some of my old handwritten slides for courses and summer schools."

Looking back, it is true that we lost a part of our working life by disposing of those boxes. Some of those notes reported on work that was "in progress", and I feel that I'll never be able to reproduce them. (The person who wrote those notes is not here anymore, and will never come back.) Does this matter? The sad truth is that it probably does not. That work would have never been finished anyway, and, even if it did, it would not have been "important enough".

Would you have made the same choice as we in our situation? Think about it before your next move.

Fulkerson Prize 2006

The Fulkerson Prize is given by the Mathematical Programming Society every three years to up to three papers in discrete mathematics. The winners of the 2006 prizes are the papers:

• Primes in P, Manindra Agrawal, Neeraj Kayal and Nitin Saxena
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries, Mark Jerrum, Alistair Sinclair and Eric Vigoda.
• Graph Minors. XX. Wagner's conjecture, Neil Robertson and Paul Seymour.

Note that Agrawal and his students have landed yet another prize for their paper after the Gödel Prize 2006 that was given to them at ICALP 2006. The third paper establishes, after work presented in twenty papers and spanning about 500 pages, the Robertson-Seymour Theorem, which has been hailed as a monumental result in graph theory and one of the deepest results in the whole of mathematics. The authors have a knack for settling long-standing conjectures in graph theory.

The winners of the Fields Medal and the Nevanlinna prize will be announced at ICM 2006 by the end of this month. I am very curious to see who will land the prizes, and whether Perelman will be awarded a Fields Medal for his work on the Poincare conjecture.

Mike Paterson's Secrets for Success

During the award ceremonies at ICALP 2006 in Venice, Mike Paterson, the recipient of the EATCS distinguished award for 2006, delivered a very witty talk in which he told the attendees his "secrets for success." Here is the short story for those amongst you who could not be in Venice to listen to Mike in person. (I apologize for any misrepresentation of Mike's message, and for being unable to match the wit and warmth in his presentation using this medium---or any other for what matters.)

Mike summarized the ingredients of his "success" as follows:

1. Start early!
2. Get lucky!
3. Hang out with smart people!
4. Enjoy what you do!
   

The first of these pieces of advice is probably the hardest to follow for many of us. What Mike meant was that at the beginning of a research field there are, I quote, "a lot of cherries ready for picking." These are problems whose solution is deemed to be important for the early development of the field and is not technically very hard. As a field matures, the open questions tend to get harder and harder, and the techniques that are brought to bear to their solutions are more and more sophisticated. Moreover, at the beginning of a research field, one can even try and steer the interests of the research community towards the problems one can actually solve.

The second point is that it does help to be in the "right place at the right time." A chat with the right person may open a lot of doors, and so can working with the right people and on a topic that is deemed to be hot at a given time. Mike gave some personal reminescences related to how he ended up working at MIT, and sharing an office, actually two offices, with Michael Fischer. Having said that, "Luck favours the prepared mind" (Pasteur), and so one should make one's own luck.

Having good collaborators is one of the most important factors in a research career. A look at our research landscape quickly reveals that more and more papers are multi-authored and are the result of a collaboration. I would recommend "hanging out with smart people" to any young researcher, no matter how smart he/she might be. There is so much to be learned in working with others!

Regarding the last point, Lance Fortnow wrote in this post that you must "Be sure to have fun doing your research because if you are not having fun you won't be successful and you can likely make more money doing something else that isn't fun." Judging from his presentations at ICALP, Mike Paterson is still having a lot of fun doing his research! Look at his recent work on the "overhang" problem with Uri Zwick to understand why. Uri Zwick is one of the "smart people" Mike likes to hang out with.

Mike's latest project is the Centre for Discrete Mathematics and its Applications. Check it out.

Thanks to Mike for setting such a good example for all of us to try and follow.