Advice for (Prospective) Graduate Students

A topic that is being increasingly covered in TCS blogs is that of giving advice to (prospective) graduate students and beginning researchers. (See, for instance, here, here or here.) This is a welcome development, and a very good way of using the medium for the benefit of an important component of our research community. (After all, young researchers are the future of research, aren't they?) In fact, I have no problem in admitting that I enjoy reading those blog posts or anything similar myself. I feel that I am still learning on the job every day, and that those pieces of advice remind me of things that I should keep in mind, but that I tend (consciously or unconsciously) to "forget". After all,

Advice is what we ask for when we already know the answer but wish we didn’t. (Erica Jong)

The latest few words of advice on research for graduate students I read have been penned down by Fan Chung. She addresses mostly combinatorialists, but what she says applies equally well to theoretical computer scientists at large. I like the fact that she stresses the collaborative nature of the research enterprise, and that she embraces one of my favourite hobby horses, viz. the Hardy-Littlewood rule: authors are alphabetically ordered and everyone gets an equal share of credit. She adds:

The one who has worked the most has learned the most and is therefore in the best position to write more papers on the topic.

(I had never thought in these terms myself, but yes that's true.) She also writes:

If you have any bad feeling about sharing the work or the credit, don't collaborate. In mathematics, it is quite okay to do your research independently. (Unlike other areas, you are not obliged to include the person who fund your research.) If the collaboration already has started, the Hardy-Littlewood rule says that it stays a joint work even if the contribution is not of the same proportion. You have a choice of not to collaborate the next time. (If you have many ideas, one paper doesn't matter. If you don't have many ideas, then it really doesn't matter.) You might miss the opportunity for collaboration which can enhance your research and enrich your life. Such opportunity is actually not so easy to cultivate but worth all the efforts involved.

I could not agree more. I will add Fan Chung's advice to the list of links I suggest to all my students and colleagues. Maybe you'd like to do so too.

Wolf Foundation Prizes for 2008

The Wolf Foundation has released the list of awardees of the Wolf Prizes 2008. Pierre Deligne and Phillip Griffiths, both of the Institute for Advanced Study, and David Mumford of Brown University, will share the 2008 Wolf Foundation Prize in Mathematics. (I note that the third of these mathematicians seem to be doing research with a high computational content these days!)

Claudio Abbado is one of the two recipients of an award in the arts. I did a quick-and-dirty Google search and it seems that none of the main Italian newspapers has devoted an article to this prize. Sadly, I am not surprised.

Concurrency Column for the February Issue of the BEATCS

I have just posted the concurrency column that will appear in the February 2008 issue of the Bulletin of the EATCS. This installment of the concurrency column is devoted to a double bill, as it offers the following two contributions:

• Part 1: Dynamic Spatial Logics: A Tutorial Survey by Luis Caires. [PDF]
• Part 2: Applying Concurrency Research in Industry: Report on a Strategic Workshop by Luca Aceto, Jos Baeten, Wan Fokkink, Anna Ingolfsdottir and Uwe Nestmann. [PDF]
  

The first piece is a survey devoted to spatial logics contributed by Luis Caires, one of the prime movers behind the development of this exciting kind of specification logics. Since the original work of Pnueli, (temporal) logics have been a prime formalism for the description of the behaviour of concurrent systems. Spatial logics are specification logics for describing the behaviour as well as the spatial structure of concurrent systems. Despite being only a fairly recent addition to the family of specification formalisms for concurrent computation, spatial logics are already the subject of a large literature reporting on a substantial body of non-trivial results. Luis Caires’s survey gives us a highly readable and welcome bird’s-eye view of this fast-moving subject.

The second contribution is a strategic report on applying concurrency research in industry. This non-technical article is one of the outcomes of the Workshop on Applying Concurrency Research in Industry, colocated with CONCUR 2007 in Lisbon, which I co-organized on behalf of IFIP WG1.8 “Concurrency Theory”. The essay tries to distil the contents of the presentations delivered at the workshop, and of the ensuing discussion, for the benefit of the concurrency community as a whole. I thank all the participants in the workshop for their contribution to the event. Special thanks go to the invited speakers (Vincent Danos, Hubert Garavel, Jan Friso Groote and Kim G. Larsen) for making the trip to Lisbon to share their considerable experience on this topic with us, and to Rance Cleaveland, Joost-Pieter Katoen, Moshe Vardi and Frits Vaandrager for providing their answers to the questions that the audience asked the invited speakers at the workshop.

I hope that you will enjoy these contributions, and that you will feel enticed to contribute to the ongoing discussion within the concurrency theory community.

Last, but not least, do contact me if you'd like to contribute a piece to the column!

Using Model Checkers in "Intro to OS" Courses

The advent of mature model-checking tools has made algorithmic model-based verification much more accessible to the average computer scientist/engineer. So much so that we can now teach first-year students to use model-checking tools by sweeping essentially all of the theory behind them under the carpet. See, for example, the very recent experience report:

Roelof Hamberg and Frits Vaandrager. Using Model Checkers in an Introductory Course on Operating Systems. Technical Report ICIS-R07031,
ICIS, Radboud University Nijmegen, December 2007.

I strongly recommend reading this report to anybody with even a passing interest in formal methods. It is well written, content rich, and presents material that can inspire many of us in the lecture room. I myself wish that the paper had been posted last August, when I was planning (at the last minute) a second-year course on Operating Systems. I would have used the authors' tips and teaching material then. Not to mention great quotes like:

“Programs are not released without being tested; why should algorithms be published without being model checked?” (Leslie Lamport)

Last November, on the spur of a sudden moment of inspiration, I did use the Uppaal model checker in a one-week intensive course on operating systems for engineering students, and the results were very encouraging.

Frits and his coauthor have done all of us a great service by making their material available on the web, and by sharing their experience with the rest of us. Let's expose our students to easy-to-use model checkers like Uppaal from the first year of the studies in CS and Engineering. This will also a increase the impact of research in formal methods. Several of the students taking my one-week course wrote in their course evaluation that they were glad to have been exposed to Uppaal, and that they think they will use the tool again in their future studies on, e.g., control systems. This indicates that, once students have seen how useful model checkers are, they will be enticed to use them later on when facing similar problems. Last, but not least, the mathematically inclined students may be motivated to carry out independent studies and (under)graduate research in formal methods and other areas of theoretical computer science.

Quoting from the concluding section of the paper:

“Why should algorithms be explained without the use of a model checker?”

Indeed, why not? It will be a good day for the construction of reliable software systems when our students will routinely simulate and analyze concurrent algorithms using model checkers. For the moment, let's share our teaching experiences following the example set by Frits and his coworker, and let's make model checking and logic permeate our undergraduate education as much as possible.

Author Contributions, Redux

Some time ago, I pointed out an article with a very detailed account of the authors' contributions. Here is another similar case I have just seen, via Galileo. (Look at the acknowledgements.) This makes me wonder whether it is standard practice in the medical literature to list what each of the authors contributed to a paper. Is it?

Knuth and Me (Guest Post by Sergey Kitaev)

Guest post by Sergey Kitaev, a very good colleague of mine from the combinatorics group at Reykjavík University.

To show the significance of Donald Knuth in my life, it would probably be enough to indicate that he introduced in 1969 the area of “permutation patterns” which is the field of my main research interest in combinatorics that I’m dealing with almost every day. However, while thinking on the subject, it comes to mind the personal communications with Knuth at Mittag-Leffler Institute at the beginning of 2005. In particular, after attending my talk on partially ordered generalized patterns, Knuth decided to include a result of mine in volume 4 of “Art of computer programming.” It is remarkable that Knuth was collecting information for this volume for over 40 years! However, this was not the thing I was offered Knuth’s famous $1.28 reward for. Unlike most other rewards, this one was not directly related to mathematics – I let Knuth know the middle name of Alexandr Kostochka that he recorded in his name database both in English and Russian (Knuth is able of writing things in Russian which he learned in college, and I find this to be impressive). In any case, stupidly enough, I refused taking the check from Knuth, which would be a nice souvenir as I realized later on; I simply told Knuth that it was a great pleasure for me to be helpful for him …

Addendum. A (permutation) pattern is a permutation of a totally ordered set. An occurrence of a pattern P in a permutation p is a subsequence of letters of p whose relative order is the same as that of the letters in P. As an example, the permutation 461352 has three occurrences of the pattern 321, namely the subsequences 432, 632 and 652.

The initial motivation for studying pattern avoiding permutations came from its connections with container data types in computer science. In 1969 Don Knuth pioneered this work by showing that the stack sortable permutations are exactly the 231-avoiding permutations.

A Free Journal-Ranking Tool

The latest issue of Nature feutures a news item reporting on a freely-available tool that can be used to generate citation statistics for papers, journals and countries. The SCImago Journal & Country Rank is a portal that includes the journals and country scientific indicators developed from the information contained in the Scopus® database. This platform takes its name from the SCImago Journal Rank (SJR) indicator, developed by SCImago, a Spanish data-mining and visualization group. This indicator is based on Google PageRank. This tool is a competitor to Thomson's Web of Science, and covers more journals (15,000 in lieu of 9,000) and 20-45% more records than the Web of Science.

The availability of this tool, as well as of Google Scholar of course, puts Thomson under some pressure. I think that this is welcome pressure. To see why, you might wish to read this editorial. Basically, the "impact factor" is one of the Gods of modern-day academia, together with "leadership" and a few other criteria not necessarily related to scholarship. It has "a strong influence on the scientific community, affecting decisions on where to publish, whom to promote or hire, the success of grant applications, and salary bonuses. " However, as claimed in the editorial, "members of the community seem to have little understanding of how impact factors are determined, and, to our knowledge, no one has independently audited the underlying data to validate their reliability." This is obviously undesirable.

I think that, for good or for worse, impact-factor-based evaluation of our research output is here to stay. However, when making decisions based on impact factor, citations and what not, I hope that deans, employers, funding agencies and rectors will consult several different sources and compare the results that they get. Moreover, I do hope that good, old-fashioned evaluation of the quality of one's work will not disappear altogether to be replaced by purely quantitative indicators.

For the moment, let's play with our new toy. In case you are interested here are the rankings of countries in computer science: all subjects, computational theory and mathematics, TCS (but as a subcategory of mathematics), logic (as a subcategory of mathematics) and mathematics as a whole.
Draw your own conclusions.

The Theoretic Centre of Computer Science

The latest issue of SIGACT News features a very entertaining piece entitled The Theoretic Center of Computer Science by Michael Kuhn and Roger Wattenhofer. This article is a "printed version of a frivolous PODC 2007 business meeting talk, held by the second author". It speculates on the central conferences and researchers in computer science, with emphasis on theory, and makes for excellent after-lunch reading. I recommend it to the readers of this blog.

In this post, I'd like to offer a couple of comments on the list of most central authors in computer science. First of all, how do Michael Kuhn and Roger Wattenhofer determine how central an author is? Here is the relevant excerpt from the paper.

Analogously to the construction of the Erdos number, we base our method on the co-author-graph. We then create the induced subgraph for each region of interest (PODC, STOC/FOCS/SODA, and computer science). For PODC, for example, this graph would only contain authors that have at least one PODC paper, and so on.

Other than in the construction of the Erdos number, we do not rely on shortest paths, but rather on the PageRank idea: We start several short random walks at different nodes of the graph, and count how often each author gets visited. This idea is then extended to time dependent centrality, by starting the random walks only at authors that have published in the last five years.

What are the results of this approach? Table 1 on page 62 of the paper gives the most central authors for computer science as a whole. Alberto Sangiovanni-Vincentelli (another Italian expat) tops the all-time list, and Noga Alon is the runner-up. Without doubt, the list contains only major players, and concurrency theorists will be happy to see Moshe Vardi at #7 on the list of most "central" authors in computer science. Some analysis of this table is provided in the paper. Here are a couple of quick thoughts and questions from yours truly.

• Computer scientists working in the area of databases feature prominently in the all-time most central authors in CS. Indeed, a look at the list of researchers with the largest number of entries in DBLP, the data set used by the authors, shows that some of the most prolific authors in CS work in that area. Could it be that people publish more and have more coauthors in the field of databases, broadly construed, than in other areas of CS?
  
• The list of most central authors does not include any Turing award winner, as far as I can tell at first sight. Does this mean that Turing award winners are not central? Of course not! To my mind, this just means that an analysis of the collaboration graph favours prolific authors with lots of coauthors. Consider, by way of example, two giants of CS research like Tony Hoare and Robin Milner, who are not even in the list of top 1000 CS authors. (Neither are Stephen Cook, Don Knuth, Gordon Plotkin or Leslie Valiant to name but a few giants, by the way :-)) By modern standards, their "number of papers" is not outstanding. However, their ideas and writings have had, and still have, enormous impact on computer science research. All of what I have done myself, for instance, is built on their original work, which has kept many computer scientists busy for about thirty years. (Of course, Robin and Tony are not responsible for the noise I have generated myself :-)) These tables are a fun read, and they do tell us something worthwhile about the players in our subject. However, as the authors point out themselves, "Without doubt the future will teach our evaluations a lesson, ultimately revealing in which direction computer science evolves, and maybe even discover the most influential computer scientist. After all, research is not about how many papers we write, or how many citations they get, but rather, what the best contributions are."
• I think that the right-hand side of Table 1 is strongly influenced by the phenomenon of name ambiguity. Consider, for instance, Wei Wang, who is ranked as #2. When I saw that Wei Wang has 86 DBLP entries for 2006, I asked myself the question: "Who is Wei Wang"? This Google search return over 1.8 million entries! It seems to me that Wei Wang is a (very large) disciple of Bourbaki or Lothaire :-)
  
• Table 2 on page 62 is a veritable who's who in the FOCS/STOC/SODA branch of TCS. It has a truly amazing number of Israeli computer scientists (six out of ten on the "all-time" list, and four out of ten on the "last-five-years" list, I believe).

Enjoy!

AMS Prizes 2008

Via the Geomblog, I see that the list of AMS prizes for 2008 is out.

First of all, let me join the chorus of congratulations for Shlomo Hoory, Nati Linial and Avi Wigderson, who have been awarded the Levi L. Conant Prize for the best expository article in the Notices or the Bulletin of the AMS in the last 5 years. They received this prize, which is a great recognition for TCS research within the mathematical community, for their article Expander graphs and their applications in the Bulletin of the AMS.

As Nati Linial says in his response for the prize

I believe that the full potential impact of combinatorics on the rest of mathematics is only starting to reveal itself and the study of expander graphs can give us some idea of the true power of these connections.

Combinatorial research is also honoured with the Leroy Steele Prize for seminal contribution to research going to Endre Szemeredi for the paper On sets of integers containing no k elements in arithmetic progression, Acta Arithmetica XXVII (1975), 199–245. I love these words in Szemeredi's response:

This award could not have occurred were it not for the fundamental work of
other mathematicians who developed the field of additive combinatorics and
established its relations with many other areas. Without them my theorem is only
a fairly strong result, but no “seminal contribution to research”.

Calling his theorem a "fairly strong result" is really faint praise, but I like the fact that Szemeredi points out that a result becomes a seminal contribution to research when it used by other researchers to obtain fruits that were considered beforehand too high on the tree of knowledge to be picked.

The prize booklet makes for some interesting reading. Wearing my Italian expatriate's glasses, I note in particular the two awards to Italian mathematicians (Alberto Bressan and Enrico Bombieri) , both of whom work in the US.

I look forward to seeing who will be the recipient of the EATCS award for 2008.

The Dangers of Blogging

In this entertaining TED talk, Yossi Vardi issues a word of warning for the male bloggers out there, and addresses the "local warming" problem.

I know that this post is somewhat different in nature from my typical ones, but it's the first day of term and a little after-lunch entertainment was called for :-)

Enjoy!

Science Magazine's Breakthroughs of the Year 2007

Anders Claesson just alerted me to the fact that Solving Checkers has been listed by Science magazine in tenth position in the list of breakthroughs of the year 2007. See here.

My colleague Yngvi Björnsson from the School of Computer Science at Reykjavík University was a member of the team behind this breakthrough. Congratulations to Yngvi and his colleagues at Alberta.