Journal Editors or Black Holes?

Sometimes journal editors (or referees) are observationally very similar to black holes. A paper is submitted, but no review escapes the force of gravity generated by the scientist in question. If the academic who is submitting the paper is well established, (s)he might not be overly bothered by this "black-hole-like effect" and live to see the day. However, in case the paper is submitted by a young scientist who might be applying for jobs, the negligence of an editor or a reviewer might have negative consequences on the career of the author of the paper.

Suppose, by way of example, that a young scientist submits a substantial paper to a high-impact journal reporting on the major findings in her doctoral dissertation. The first review round takes a whole year, despite repeated enquiries to the handling editor, and the editor asks for major revisions based on the detailed referee reports. The author works hard at handling the suggestions from her reviewers, and submits a revised paper. One more year passes and the email enquiries by the author receive no answer from the cognizant editor.

What would be the best line of action for the young scientist in question? Should she wait for a second bunch of reports, which might never come, or would she be best served by withdrawing the paper and submitting it elsewhere? What advice would you give in a situation like this one?

What Are The Hot Research Areas in Concurrency Theory?

Yesterday Andrei Sabelfeld (Chalmers University of Technology, Sweden) visited ICE-TCS with Arnar Birgisson, a former master student of mine who is now doing doctoral studies under his supervision. Andrei delivered the seminar Information flow in web applications in the ICE-TCS seminar series (the abstract for the talk is here), we talked about liveness and safety properties and about academic matters in general. We at ICE-TCS enjoyed his visit a lot.

Over dinner,  Andrei asked me:

• What are the big unsolved problems in concurrency theory?
• And what are the hot research areas in the field?

I gave my quarter-baked personal answers, but I'd like to hear yours.

I have the feeling that research in concurrency theory is driven more by "hot research areas" than by collections of big open problems, but that's just my personal impression, even though at some point I started collecting a list of open problems and stated some in this essay. 

Also, how much does the "hotness of a research area" inform the research you do and that you suggest to your students? For what it is worth, for good or for worse, I mostly tend to follow my own personal interests and inclinations rather than the directions of the field at large. However, one  has to "sell" one's work and have it published. It is undoubtedly easier to do so if the work is considered to be hot and timely by a substantial fraction of the research community. Doing work in areas that are considered "important" by many will probably also give a student better opportunities to find further employment.

Overall, I feel that it is important to give one's students a good problem to work on for her/his dissertation. There are certain characteristics that a good problem should have for sure, but is "hotness" one of those?

Addendum: There is a lot of good career advice for everyone here.

LICS 2010 Accepted Papers and Martin Grohe's Latest Opus

The list of accepted papers for LICS 2010 is out. As usual, the programme looks very interesting and exceedingly strong.

For an interested, but not very knowledgeable, observer like me, one of the most interesting looking papers that have been selected for the conference seems to be yet another seminal contribution by Martin Grohe. The paper is Fixed-Point Definability and Polynomial Time on Graphs with Excluded Minors.

From the abstract of that ten-page paper, I learn that Grohe proves that fixed-point logic with counting captures polynomial time over all classes of graphs with excluded minors. To my untrained eye, this looks like an amazing result. The proof of this theorem will take up the whole of this monograph, which is currently being written and will be well over 200 pages long. The current draft spans 238 pages.

Would such a result meet the current requirements for the Gödel prize, say? It seems to me that it would not, unless Grohe also publishes a journal paper based on a fragment of his monograph. Taking the view that proofs of certain results are likely to be very long and that very few journals in computer science would publish papers that are 250 pages long, say, would it not be reasonable to let a research monograph qualify a piece of research for the Gödel prize? After all, if the result is important, it will be studied in depth by many researchers, ensuring a more thorough level of peer review than the one obtained via a standard refereeing process for a journal.

The loss of a giant: Robin Milner has passed away

I just read the following message from Gordon Plotkin. This is really sad news. I plan to post a more elaborate message soon, but we have lost another intellectual giant, a gentleman and a true inspiration for us all.

-----------------------------

Dear Colleagues,

I am deeply saddened to pass on the following message from Barney and Chloë Milner:

"We are sorry to announce that Robin Milner died on Saturday 20th March, in Cambridge, just three days after the funeral of his wife, Lucy.

He will be greatly missed by his family and friends, as well as the academic community."


Gordon Plotkin

SOS 2010

I am co-chairing SOS 2010 (Structural Operational Semantics 2010) with Pawel Sobocinski (Southampton). The call for papers has been posted on several mailing lists and all the information on this workshop, which is affiliated with CONCUR 2010, is available from the workshop's web site.

Consider submitting a paper and join us in Paris on August 30 to discuss the latest research on Structural Operational Semantics! I have a series of long-overdue posts describing some of the recent work by my co-authors and me on this topic. I hope to find some time to write those posts after the teaching is over and I have cleared my desk a little.

First Clay Mathematics Institute Millennium Prize Announced Today

It looks like the Clay Mathematics Institute (CMI) is parting with its first one million USD. Indeed, today the CMI  announced that Grigoriy Perelman is the recipient of the Millennium Prize for the resolution of the Poincaré conjecture. Full details are here and a full-length press release is also available. 

What do you think will be the next Millennium Prize Problem to fall? It seems very unlikely that it will be our own P vs. NP problem, but, as Bohr taught us,  “Prediction is very difficult, especially about the future".  

Magnús Halldórsson receives the first Reykjavík University Research Award

This is a belated post on a piece of news that is mostly of local (read, Icelandic) relevance. However, I think that TCS researchers everywhere will be pleased to know that the first research award from Reykjavík University, where I have worked since November 2005, has been given to Magnús M. Halldórsson, for his work on approximation algorithms for computationally hard problems, amongst others. (The announcement in English is here.)  It is good to see the first research award go to a TCS researcher, also because this sets high standards for future such awards.

It will be interesting to see whether future award committees will be influenced by considerations related to "academic politics" in selecting awardees for the university research award. If not, I expect to see a few awards in the coming years go to people working in (T)CS and combinatorics.

Belated congratulations to Magnús.

Two PhD Studentships Available

Yesterday night, I posted the appended announcement of two PhD studentships, which became available thanks to a successful grant application to the Icelandic Fund for Research (Rannis), on a couple of mailing lists.

I am posting it here too, just in case any of the readers of this blog is interested in applying or has any student who would be a suitable candidate for the studentships.

---------------------------------------------------------

            Meta-Theory of Algebraic Process Theories

         School of Computer Science, Reykjavik University

          Two PhD studentships

Applications are invited for two PhD studentships at the School of Computer Science, Reykjavik University.  The positions are part of a three-year research project funded by Rannis (the Icelandic Fund for Research), under the direction of Luca Aceto and Anna Ingolfsdottir.

Aim of the project

Algebraic process theories, also known as “process algebras”, are prototype specification languages for reactive systems—that is, for devices that compute by reacting to stimuli from their environment. The main strength of such theories lies in the equational (calculational) style of reasoning they support. For each process theory, several natural questions immediately arise pertaining to the (non-)existence of (finite or recursive) sets of laws that allow one to prove by “substituting equals for equals” all of the valid equalities between process descriptions (closed or open terms) over fragments of the process theory at hand. Currently, answering such questions is only possible via delicate, error-prone and lengthy proofs.

The aim of the project is to contribute further advances to the study of the meta-theory of algebraic theories of processes.  The main goals of the project are

• to establish a generic framework for answering questions pertaining to the existence of equational axiomatizations of behavioural semantics over process algebras affording certain desirable properties, such as being finite or recursive, and
  
• to apply the proposed general theory to solve some of the main open problems in the study of the equational logic of processes.
  

Research environment

The research  within the project will be carried out in close collaboration with our long-term co-workers Wan Fokkink (VU Amsterdam), Bas Luttik (TU Eindhoven), MohammadReza Mousavi (TU Eindhoven) and Michel Reniers (TU Eindhoven).

The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). ICE-TCS has currently 14 permanent members, seven postdoctoral researchers and one Ph.D. student.  For more information about ICE-TCS, its members and its activities, see http://www.icetcs.ru.is/.

Qualification requirements

Applicants for the PhD studentships should have a good MSc degree in Computer Science, Mathematics or closely related fields, and have a strong background in discrete mathematics and formal systems. Some previous knowledge of topics from at least one of concurrency theory, process calculi and structural operational semantics is not a prerequisite, but would be desirable.

Remuneration

PhD position: 265,000 ISK (roughly 1,550 euros) per month before taxes, for three years, starting as early as possible and no later than October 2010.

Application details

By Friday, 26 February 2010, interested applicants should send their CV, including a list of publications where applicable, in PDF to the addresses below, together with a transcript of their academic record, a statement outlining their suitability for the project and the names of two referees.

Luca Aceto
email: luca@ru.is

Anna Ingolfsdottir
email: annai@ru.is

We will start reviewing applications as soon as they arrive, and will continue to accept applications until the positions are filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.

About the School of Computer Science at Reykjavik University

The School of Computer Science at RU (http://www.reykjavikuniversity.is/computer-science/) has approximately 440 students at the undergraduate, masters and doctorate levels. The School is home to several strong research groups and the main research areas are algorithmics, artificial intelligence, combinatorics, concurrency theory, databases, human-computer interaction, natural language processing, software engineering, theoretical computer science and virtual environments.

The School of Computer Science at Reykjavik University  has ties with several leading foreign universities, facilitating collaboration, as well as faculty and student exchanges. In particular, the School has a joint M.Sc. degree in Computer Science with the University of Camerino, Italy, and a joint Ph.D. degree programme with KTH, Stockholm, Sweden.

Information about Ph.D. studies at the School of Computer Science is available at

http://www.reykjavikuniversity.is/departments/school-of-computer-science/ph.d-studies/

Concurrency Column for the February 2010 Issue of the BEATCS

I have just posted the paper for the concurrency column that will appear in the February 2010 Issue of the BEATCS. This installment of the concurrency column is devoted to a very informative survey, contributed by François Laroussinie, of recent work on the modelling and specification of open systems using games and alternating-time temporal logics. In particular, the paper focuses on fundamental semantic questions for those specification formalisms, such as the kind of properties that can be stated in various types of logics for games, and on the computational complexity of their model-checking problems. Enjoy it!

My New Workplace

The School of Computer Science has moved into its premises in the new building of Reykjavik University. The building is still a construction site, and will remain so for a few more months at least. You can see some photos here. There is no doubt that the building looks good. However, I am not so sure that it will offer the best working conditions for academic work. For instance, as a consequence of the downsizing of the building because of the economic crisis in Iceland, we have no offices and we are all sitting in an open space. (I'll try to post a photo of the TCS area when I get a chance to take one.)

I am not passing judgement yet on the effect that this will have on my work. The next few weeks will allow me to form an opinion on this issue. I will try to keep an open mind and to make the most of what I have available. However, it is hard to escape the nagging thought that I had a quieter working environment when I was a Ph.D. student.

Stay tuned for more information.

Job Announcement: Dean of the School of Computer Science at Reykjavík University

The School of Computer Science at Reykjavík University, my own stamping ground, is seeking a new dean. Our present dean, Ari K. Jónsson, will take over the rectorship of the university on January 23, 2010, and we are looking for excellent candidates to take over the deanship of the school. (The dean has direct responsibility for academic, administrative and fiscal operations of the School of Computer Science. The dean is part of the executive committee of the university and reports directly to the rector.)


The School of Computer Science hosts several active research groups and its main research areas are artificial intelligence, combinatorics, databases, human-computer interaction, natural language processing, software engineering, theoretical computer science and virtual environments.
 

The job announcement is here. Is any of you out there interested in applying for the job?

A Question on the Structure of Fields, Centres and Committees

Can anyone briefly explain to me, or point me to on-line information about, the raison d'être and operating characteristics of structures like the fields and centres at Cornell and MIT, or the interdisciplinary committees found at the University of Chicago?

I am asking wearing my hat of the chairman of the research council of my university, where we are mulling about the possibility of having similar structures. Thanks in advance for any information you might be able to provide!

Tony Hoare on Industrial vs. Pure Research

I have just read a very cogent retrospective piece that Tony Hoare has written for the October 2009 issue of CACM to mark the 40th anniversary of the publication of his seminal paper An axiomatic basis for computer programming. (This is the first article he wrote as an academic. Not a bad way to start, is it?) It is a read that I thoroughly recommend and that I'll make available to the students who are now taking my course on the semantics of programming languages. I am posting an excerpt from that viewpoint article on industrial vs. pure research in computer science since it may be of interest to readers of this blog. I pass the word to Tony.

"Pure academic research and applied industrial research are complementary, and should be pursued concurrently and in collaboration. The goal of industrial research is (and should always be) to pluck the 'low-hanging fruit'; that is, to solve the easiest parts of the most prevalent problems, in the particular circumstances of here and now. But the goal of the pure research scientist is exactly the opposite: it is to construct the most general theories, covering the widest possible range of phenomena, and to seek certainty of knowledge that will endure for future generations. It is to avoid the compromises so essential to engineering, and to seek ideals like accuracy of measurement, purity of materials, and correctness of programs, far beyond the current perceived needs of industry or popularity in the market-place. For this reason, it is only scientific research that can prepare mankind for the unknown unknowns of the forever uncertain future.

So I believe there is now a better scope than ever for pure research in computer science. The research must be motivated by curiosity about the fundamental principles of computer programming, and the desire to answer the basic questions common to all branches of science: what does this program do; how does it work; why does it work; and what is the evidence for believing the answers to all these questions? We know in principle how to answer them. It is the specifications that describe what a program does; it is assertions and other internal interface contracts between component modules that explain how it works; it is programming language semantics that explains why it works; and it is mathematical and logical proof, nowadays constructed and checked by computer, that ensures mutual consistency of specifications, interfaces, programs, and their implementations. There are grounds for hope that progress in basic research will be much faster than in the early days. I have already described the vastly broader theories that have been proposed to understand the concepts of modern programming. I have welcomed the enormous increase in the power of automated tools for proof. The remaining opportunity and obligation for the scientist is to conduct convincing experiments, to check whether the tools, and the theories on which they are based, are adequate to cover the vast range of programs, design patterns, languages, and applications of today's computers. Such experiments will often be the rational reengineering of existing realistic applications. Experience gained in the experiments is expected to lead to revisions and improvements in the tools, and in the theories on which the tools were based. Scientific rivalry between experimenters and between tool builders can thereby lead to an exponential growth in the capabilities of the tools and their fitness to purpose. The knowledge and understanding gained in worldwide long-term research will guide the evolution of sophisticated design automation tools for software, to match the design automation tools routinely available to engineers of other disciplines."

Amir Pnueli Dies

I just learned via a posting on the TYPES mailing list the sad news that Amir Pnueli, one of the inspirational and leading figures in several areas related to the formal specification and verification of computing systems, passed away yesterday at age 68. An email message circulated yesterday by his family states that "Amir has suffered a serious brain hemorrhage which he could not recover from. He passed away today [2 November] at noon."

In 1996, Pnueli received the Turing Award for seminal work introducing temporal logic into computing science and for outstanding contributions to program and systems verification.

His scientific legacy will be felt for many years to come.

Benchmarking Metrics: What and Why?

In his post entitled "Top 10 theory schools?", Jonathan Katz gives a list of what he considers to be the top 10 theory departments in the US. (Read the post and the comments for an update on the discussion.) One of the comments reads as follows:

I would agree about:


MIT (Silvio, Shafi, Ron, Michel, …)
Cornell (Rafael, Eva, Jon, Bobby,…)
Berkeley (Luca, Christos, Umesh,…)
CMU (Venkat, Manuel, Avrim, Ryan,…)
Princeton (Boaz, Sanjeev, Moses, Bernard,..)

The others are a bit flakier:

GA Tech (Santosh, Chris, Vijay, Sasha, …)
UT Austin (Adam, David, Brent)
UCSD (Mihir, 1/4 Russell, Daniele, maybe Hovav)
U Washington (Anna, Paul, Anup)

I would say at least he following schools are VERY comparable to above:

Stamford (Dan, Serge, Tim, Amin,…)
NYU (Subhash, Assaf, Yevgeniy, Richard, …)
Harvard (Salil, Michael(s), Leslie)
Columbia (Mihalis, Rocco, Tal)

I would say there are top 5, and then top 10 following them.

So this commentator measures the quality of a theory group using the perceived research quality of the very best researchers at a given institution. Another possible metric would be the size of the group of active researchers with high international visibility. Yet others could be the number of peer-reviewed publications in top-class journals and conferences, or the average such number per staff member.

What criteria are most useful and why (bearing in mind that, at the end of the day, we are always making subjective judgements)? I am interested in this topic since the School of Computer Science I am working at is presently undertaking a benchmarking exercise. The aim of the exercise is to find three to four departments in the Nordic countries with which we aim at comparing ourselves in the very short term, within five years and within 10-15 years. One of the interesting aspects of this exercise is that our school is substantially smaller than most of the departments elsewhere. So, what do you think would be good metrics for the benchmarking exercise? Standing of the top scientists within the school? Average number of peer-reviewed publications and citations? Or what?

EATCS Award 2010: Call for Nominations

The Call for Nominations for the EATCS Award 2010 has been published (see this pdf). Nominations and supporting data should be sent to the chairman of the EATCS Awards Committee, Emo Welzl. The next award is to be presented during ICALP'2010 in Bordeaux. The deadline for nominations is: December 15, 2009. So get your act together quickly and nominate one of the many "obvious suspects" for the award! 

Note that nominations are now kept alive for three years. Since I sent in an unsuccessful nomination last year, I don't need to do anything this time around and will just be a very interested observer :-)


I wish the award committee the best of luck with their work.

Five Years of Logical Methods in Computer Science

I have received this letter via email. I post it here since I strongly support journals like LMCS and I encourage my readers to submit good papers to it. Happy birthday LMCS! May your reputation grow with the years.



Dear Colleague:

We would like to bring the community up to date on the journal

   Logical Methods in Computer Science
   www.lmcs-online.org

We started this fully refereed, open access, free electronic journal in January 2005, intending to create a high-level platform for publications in all theoretical and practical areas in computer science involving logical methods, taken in a broad sense. We are now on Issue 3 of Volume 5 (there are four issues a year). So far, we have received more than 350 submissions of which we have published 162. In addition to individual submissions, our journal publishes special issues, e.g., of selected papers of high-level international conferences such as LICS, IJCAR, CAV, CSL, and RTA.

We are continuing actively to develop the journal. For example, we accept survey articles, and are developing `live' surveys, which can be continually updated as knowledge progresses. In another direction, we are considering allowing authors to provide additional material of an expository nature, such as slides and videos, to enable them to interest a wider spectrum of readers in their contribution.

The journal is an overlay of CoRR, the computer science repository of arXiv. There are no fees for authors nor for readers. Every paper is refereed by two or more referees, and high standards are applied. The editorial board consists of about sixty top specialists in all areas of logic in computer science.

The journal is covered by Mathematical Reviews, the ISI Web of Knowledge, and the DBLP Database.

We welcome your comments and suggestions, and we seek your contributions! For more information please consult our web pages:

     www.lmcs-online.org

Yours,

Editor-in-Chief:   Dana S. Scott <dana.scott@cs.cmu.edu>
Managing Editors:  Benjamin C. Pierce <bcpierce@cis.upenn.edu>
                  Gordon D. Plotkin <gdp@inf.ed.ac.uk>
                  Moshe Y. Vardi <vardi@cs.rice.edu>
Executive Editors: Jiri Adamek <adamek@iti.cs.tu-bs.de>
                  Stefan Milius  <s.milius@tu-bs.de>

IFIP 1.8 workshop on FORMAL METHODS FOR EMBEDDED SYSTEMS

I have received the following announcement from Bas Luttik. I am happy to post it here since the event will be of interest to concurrency theorists and people working on formal methods at large, many of whom will be in Eindhoven for FM week.  (Not to mention the fact that I am the outgoing chair of IFIP WG 1.8.)

==============================

========================================
                       CALL FOR PARTICIPATION
======================================================================
      IFIP 1.8 workshop on FORMAL METHODS FOR EMBEDDED SYSTEMS

               http://www.cse.unsw.edu.au/~rvg/FMES/

           Eindhoven, The Netherlands, November 5, 2009
======================================================================

This IFIP 1.8 workshop is organised as part of the Formal Methods Week,
which takes place in Eindhoven from November 2 until November 6, 2009.
The goal of the workshop is to summarise research from different areas
of formal methods targeted to embedded systems, and to promote the use
of formal methods in different applications and in the engineering
discipline for embedded systems.

PROGRAMME:
----------
 8:30  Registration and coffee
 8:50  Opening

 9:00  Bert van Beek -
         The Compositional Interchange Format: concepts, formal basis,
         and applications
 9:45  Holger Hermanns -
         Synchronous vs. Asynchronous Performance Models of Industrial
         Networks on Chip Designs

 10:30 Coffee break

 11:00 Catuscia Palamidessi -
         Synchronization in the pi-calculus
 11:45 Joost-Pieter Katoen -
         Analysis and Semantics of Extended AADL Models

 12:30 Lunch
 14:00 The End

For abstracts of the talks and further details about the workshop we
refer to http://www.cse.unsw.edu.au/~rvg/FMES/.

REGISTRATION
------------
The registration fee for the workshop is 45 euros and covers coffee/tea
and lunch. You also need to register for FMweek, which costs an
additional 35 euros (administration costs). Please register via the
FMweek website: http://www.win.tue.nl/fmweek

WORKSHOP ORGANISERS:
---------------------
Rob van Glabbeek (National ICT Australia)
Ursula Goltz (Technical University Braunschweig, Germany)
Bas Luttik (Technische Universiteit Eindhoven, The Netherlands)
Uwe Nestmann (Technical University Berlin, Germany)

Presburger Award

In an old post I announced that the EATCS was about to initiate a young researcher award. I am happy to see that the call for nominations for the first Presburger Award has now been advertised. See here for the details. The award is meant for scientists in TCS who are 35 or younger.

The award is named after Mojzesz Presburger who accomplished his ground-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.

The award includes an amount of 1000 € and an invitation to ICALP 2010 for a lecture.

I hope you will take the time to nominate young scientists for the award. Who would be your favourite candidates?

Treatment of Alan Turing was “appalling”

Arnar Birgisson, a former MSc student of mine who is now a PhD student at Chalmers, pointed out to me that last Thursday Gordon Brown issued a statement "recognising the “appalling” way he [Alan Turing] was treated for being gay." The piece of news may be found here.

It is understandable that Gordon Brown's statement focuses on Turing's work on breaking the German Enigma codes. However, I find it suprising that Turing's role in the development of computer science does not deserve any mention at all in the apology.

The statement ends as follows:

"So on behalf of the British government, and all those who live freely thanks to Alan’s work I am very proud to say: we’re sorry, you deserved so much better."

So long, and thanks for breaking the Enigma code, devising the Turing machine and the universal Turing machine, building some of the earliest programmable computers and all the rest.....