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.

ICALP 2008

Last Tuesday, the EATCS general assembly held at ICALP 2006 in Venice has accepted the bid presented by Magnús M. Halldórssón on behalf of ICE-TCS to hold ICALP 2008 in Reykjavík. Anna, Magnús and I look forward to seeing you in Iceland in July 2008.

I'll try to report on a couple of interesting events at ICALP 2006 over the next few days. For the moment, I'll just say that Manindra Agrawal received the Gödel Prize 2006, and that Mike Paterson received the EATCS distinguished award. Mike's entertaining talk let us in on his "secrets for success." His presentation will need a separate post, even though I am pretty sure that you are already wondering what his secrets are :-)

ICALP Report

So Italy brought the Fifa World Cup 2006 home after 24 years. I am biased on this issue, so I won't comment on Italy's win. For an independent opinion, you might wish to check out this article from the Guardian. (Allow me to say, however, that, not surprisingly, I am glad Italy won the championship :-))

I am now at ICALP 2006, and will be attending the General Assembly in about 45 minutes. For the moment, I can give you a couple of possibly interesting news regarding the EATCS. First of all, the new president of the EATCS is going to be Giorgio Ausiello. Mogens Nielsen (the former president) and Paul Spirakis will act as vice-presidents. There are going to be some interesting developments in the role that the EATCS will play for the development of Theoretical Computer Science as a whole. A small, but I believe very important, first step is the free access experiment for the Bulletin of the EATCS, which will begin asap. This will make the Bulletin a more widely read, and I believe better quality, publication.

I'll keep you posted on other developments related to publications and EATCS prizes in due course. News regarding the location of ICALP 2008 will follow soon.

Off to ICALP in Venice

I am off to ICALP 2006 in Venice tomorrow, and hope to get to Venice in time to watch all of the World Cup final---even though watching the match will make me suffer as I always do when Italy are playing.

On Monday I'll attend the EATCS Council meeting, where I expect interesting discussions on whether the Bulletin should be freely available to all on the web, and the issue of EATCS prizes. My opinion, and one that I'll argue for at the meeting, is that the Bulletin should be freely available on the web in its entirety, just like the Notices of the AMS---whose electronic publication is supported by the members' dues. This will help us reach a wider audience, and further increase the visibility of TCS.

On Tuesday afternoon, during the EATCS general assembly, Magnus Halldorsson, Anna Ingolfsdottir and I will present a bid on behalf of ICE-TCS to host ICALP 2008 in Reykjavik, Iceland. If you are in Venice, make sure you attend the assembly and vote for us :-)

I'll try to report on these meetings and on the conference at a later time.

How We Should Not Behave

I encourage all of you to take a deep breath and read the comments to this post by Lance Fortnow. Reading also the comments to this one won't hurt. Then draw your own conclusions.

I'll refrain from further comments, but thanks to Boaz Barak and Luca Trevisan for their thoughtful contributions.

Outstanding Young Researchers on the Horizon

It is a humbling experience to see young stars in our research world shine very brightly and very fast.

Yesterday, while reading the comments to this post by Lance Fortnow, I learned that Mihai Pătraşcu, the author of three accepted papers at FOCS 2006, is a first-year graduate student, and submitted the papers when he was still an undergraduate at MIT! He was also the co-recipient of the best Best Student ICALP Paper for 2005.

Earlier this year, Jacob Fox (MIT) won the Frank and Brennie Morgan Prize for Outstanding Research in Mathematics by an Undergraduate Student. (See this link.) The prize citation mentions that:

Jacob Fox’s research exhibits a formidable ability to get to the heart of the issues in the problems at hand, and the ability to develop extremely ingenious and novel techniques. In addition to being able to solve problems posed by others, Fox has also excelled at finding topics all by himself, formulating novel conjectures and approaches to solutions. His accomplishments are shaping his areas of research, and are of extraordinary promise for the future.

If you want to read about one of the things he has done, look here. (Make sure you don't miss Dana Scott's feedback to that post!)

I am always overawed by these accomplishments from young researchers, and wish both Mihai and Jacob the best of luck in fulfilling their exceptional promise. However, no matter how gifted they are, it is a fair bet that this won't be easy. They will have to show a lot of appetite for hard work and guts in doing so. Keep it up guys!

Before closing, and in Football World Cup spirit, let me suggest that you have a look at this short movie by Marcus du Sautoy, professor of mathematics at Oxford University, where he uses football to explain the proof of Euclid's theorem to the effect that there are infinitely many prime numbers. Marcus du Sautoy is the author of the excellent book The Music of the Primes. Check it out, if you have not read it already.

FOCS 2006 Accepted Papers

The list of accepted papers for FOCS 2006 (47th Annual Symposium on Foundations of Computer Science) is now available. A brief look at the list seems to indicate the absence of "Volume B" papers. I do not know whether this is due to the lack of submissions to that conference from "Volume B" researchers, but I find it sad that a very prestigious conference with that name has no papers on, for instance, applications of logic to CS.

I am glad to see that there is a paper co-authored by BRICS colleagues of mine, namely

Improved Dynamic Planar Point Location
by Lars Arge and Gerth Stolting Brodal and Loukas Georgiadis

Congratulations to Lars and Gerth!

An Eight Page Paper of Kleene

In his article Stephen Cole Kleene - a reminescence, Saunders Mac Lane quotes a letter from Kleene to his mother. In that letter, Kleene wrote:

"Rosser and my article is deadly. It is only 8 pages typed....,but it would require reading a couple of hundred pages perhaps to make full check up on it all. One sentence takes 10 pages to prove."

Alas, the piece does not say what paper of Kleene's the letter refers to. However, no matter what paper it was, I do not believe that that type of distillation is ever useful when writing a paper. Who could claim to understand those 8 pages after all?

Addendum: One of my readers pointed out that the essay does point out the title of the paper. It is

Kleene, S. C.; Rosser, J. B.
The inconsistency of certain formal logics.
Ann. of Math. (2) 36 (1935), no. 3, 630--636.

The paper is available online from: http://www.jstor.org/view/0003486x/di961655/96p00874/0.


Thanks to the anonymous reader, and shame on me for not checking my sources as thoroughly as I should have done, and trusting my untrustworthy memory.

Goal: To Be Amongst the Top 100 Best Universities

On Thursday, 31 May, Magnús Halldórsson invited some of the participants at our second ICE-TCS theory day for a barbeque at his house. This was a very pleasant evening, and a fitting end to a very satisfying day from both a social and a scientific point of view.

During the course of the evening, Moshe Vardi regaled us with some of his interesting opinions on all kinds of academic issues, some of which he has aired in a very stimulating SIGMOD RECORD interview. (See Moshe Vardi Speaks Out (on the Proof, the Whole Proof, and Nothing But the Proof) by Marianne Winslett. SIGMOD RECORD, Volume 35, Number 1, March 2006. Do read it!)

One of the things Moshe said was that the goal of improving a department's/university's ranking in one of the many rankings of academic institutions that are available today is not a realistic one. One should focus on measurable goals that one has some form of control over---for instance, increasing the number/quality of graduate students, or the number of papers published by members of staff in, say, I&C and TCS, or whatever else is deemed to lead to a measurable improvement in the institution. Moshe says in that interview that he never felt that the goal of ranking improvement was attainable or useful.

While hearing him air these opinions, I was reminded of the recent pronouncement by the rector of the University of Iceland, who said that by 2010 that university should be ranked amongst the top 100 in the world. This is a very tall order, and I believe that it is not achievable with the economic and human resources that are available for that institution, or any other university in Iceland for what matters.

What might turn out to be useful in setting the university such a lofty goal is the process of change in its daily academic life that this will entail. To be a top 100 university, the percentage of "research active" members of staff will have to increase considerably, the quality of the publication outlets of most members of staff will have to improve, and there will have to be a push towards research that is recognized internationally. Publishing scientific articles in Icelandic in the single Icelandic scientific journal won't be enough for getting tenure or promotion.

However, setting an unachievable goal may also have a negative psychological repercussion. What will the reaction of the staff members be when they will double, say, their scientific output both in quality and quantity, and then discover that their university is still not ranked amongst the top 500 in the world, let alone amongst the top 100? I would not be amused myself. Worse still, people might feel that their efforts have been in vain, and get back to the old, cosy mould.

University administrators, like army generals or chiefs of staff, should also think about the morale of their troops, who are, after all, those who do battle in the classroom and in the scientific arena on a daily basis.

NWPT'06 in Reykjavík

Yesterday Anna and I sent the preliminary announcement for the Nordic Workshop on Programming Theory 2006 that we'll organize at Reykjavík University to several mailing lists. Most likely if you are reading this post, you will receive one or more of our announcements. Still I cannot resist advertising the event using this medium.

The NWPT'06 workshop will take place in the period 18-20 October. This is the 18th installment of this event, which is a forum bringing together programming theorists from the Nordic and Baltic countries (but also elsewhere), and the first time that the workshop will be held in Iceland.

The scope for the workshop mentions several topics of interest to concurrency theorists, and the list of invited speakers includes Gerd Behrmann, Matthew Hennessy, Hanne Riis Nielson, and David Sands.

If you wish to give a talk at the workshop, all you have to do is to submit an abstract of 1-3 pages (ps or pdf, printable on A4 paper) to nwpt06(at)ru(dot)is by the 19th September 2006. Submission of work submitted for formal publication elsewhere and work in progress is permitted.

The abstracts of the accepted contributions will be available at the workshop. After the workshop, selected papers will be published in a special issue of Nordic Journal of Computing.

Why don't you use this opportunity to visit Iceland?

Two-Body Problem

Last Monday's post in Lance Fortnow's excellent blog addressed the two-body problem. This is the problem that academic couples have to solve in finding (academic) jobs in the same city. It is not an uncommon problem at all in Computer Science, and sometimes departments/universities showing a willingness to help solve instances of this problem greatly improve the quality of their academic staff in the process. For instance, Kári Ragnarsson (a member of my extended family and a blossoming algebraic topologist who has a two-body problem himself) tells me that the Department of Mathematical Sciences at the University of Aberdeen has benefited by solving two instances of the two-body problem. Lance Fortnow himself hints at the solution of two-body problems as being one of the factors in the rise of the theory group at Georgia Tech.

One of the readers of Lance's blog points out that:

In Germany the two body problem is so bad that many academic couples have resigned themselves to living apart and commuting back and forth on the weekends.

The situation described in the last comment is not limited to Germany. My understanding is that the same applies in Italy too. The two-body problem becomes even more difficult in Italy when one of the academics involved is not Italian. I know personally of at least two instances of the two-body problem involving one Italian and one non-Italian that could be solved abroad (twice and in two different countries in both cases), but apparently not in Italy. No doubt there are many more examples.

As with all problems of this type, there are no silver bullets to a solution. One has to try and work things out in the best possible way, without sacrificing one's family life too much---assuming that having a family life is a priority for the people involved, of course. (And this is even harder when there are children involved.) However, I find it surprising that institutions/universities that do not have such a high standing are not willing to take the plunge and help scientists solve two-body problems that would improve their quality. My message to the heads of department of those institutions would be that being creative in this and other situations might make it possible for them to attract excellent academic staff members that would normally not even consider applying for a job at their institutions.

Post Scriptum: Above I wrote that two body-problems are not uncommom. I already mentioned Kári and his girlfriend (algebraic topology marries combinatorics). Two of my very best collaborators (Wan Fokkink and Bas Luttik) also live with computer science researchers (Judi Romijn and Simona Orzan, respectively). Of course, I should not forget couples like Dale Miller and Catuscia Palamidessi, or Orna and Raz Kupferman. This is only the tip of the iceberg, I believe, and somewhere inside that iceberg one can also find Anna and me.

Finite Basis for CCS

After a long sabbatical from conference submission (at least by the standards of present day Computer Science), I have two papers accepted at ICALP'06 in Venice. I have already reported on one of them on this diary. The other paper, entitled A Finite Equational Base for CCS with Left Merge and Communication Merge is joint work with Wan Fokkink, Anna Ingólfsdóttir and Bas Luttik, and the full version is available as a BRICS report. In that paper, we provide a complete equational axiomatization of bisimulation equivalence over the relabelling-, restriction- and recursion-free fragment of CCS, enriched with the left and communication merge operators proposed by Jan Bergstra and Jan Willem Klop. The axiomatization is complete in the sense of classic universal algebra---that is, it can prove all of the valid equations, whose terms may contain variables---and consists mostly of standard equations that had been considered in previous related work. The proof strategy is also based on the classic approach based on normal forms. However, the devil and the pudding are in the details that need to be worked out in order to make the general proof strategy "work" in the specific setting. A lot of care needs to be taken in defining a suitable notion of distinguishing substitution, and in proving that our hunches do work.

I find this result satisfying, and look forward to hearing Bas's ICALP talk based on it. Once again, thanks a lot to my co-authors for a very pleasant and instructive collaboration.

H is the Magic Number

Humans seem to like metrics of all sorts, and we tend to develop and apply them also to subjects that do not naturally lend themselves to "objective measurement". George David Birkhoff wrote a book entitled Aesthetic Measure (1933) to develop a mathematical theory capable of measuring the aesthetic value of a piece of art. (See this nice little article to get an idea of the gist of Birkhoff's proposal.)

In our age in which "impact" and "leadership" are two of the main gods of academia, we are trying to do the G.D. Birkhoff and develop all kinds of metrics to determine how valuable our research is. The discussion of whether these metrics are any good at all, and whether they should be used in evaluating applicants for positions/promotion etc., would need a series of posts. Here I just want to point out one of these metrics.

Jorge Hirsch developed the h-number as a measure of the scientific output of a researcher. Being curious, many of us, including yours truly, will immediately try to determine (an approximation to) their h-number. This is now easy to do, thanks to a a script written by my BRICS colleague Michael I. Schwartzbach (University of Aarhus), which consults Google Scholar. Here is Michael's web interface.

According to Michael's script, my h-number is something like 14. This is far off from the h-number of people among the h-number elite maintained by Jens Palsberg (UCLA), but then again anything else would have been a major surprise to me.

Enjoy computing your h-number and those of your friends/competitors, but please resist the temptation of reading too much into this or any other metric.

[In case you are wondering where the title of this post comes from, I can tell you that it is based on the title of the second song in 3 Feet High and Rising, the debut album from American hip-hop trio De La Soul. In that song, "the magic number" was, guess what, three.]