One year of Electronic Proceedings in Theoretical Computer Science (EPTCS)

Electronic Proceedings in Theoretical Computer Science (EPTCS) was launched by Rob van Glabbeek in 2009, as an initiative to have proceedings of all worthy workshops in Theoretical Computer Science freely available on-line. The papers in the proceedings are simply entries in the CoRR repository. DOI numbers are assigned to EPTCS publications, and they are indexed in CrossRef and in the Directory of Open Access Journals.  There is no charge for authors or workshops/conferences.

The idea caught on like wildfire, and since EPTCS was launched over 30 proceedings were published, and 22 more have been accepted for publication.

Perhaps one of the reasons is that the procedure for submitting a proposal is very simple, and our response time to a proposal is very fast, usually less than 10 days. Additionally, thanks to efficient workflow, proceedings usually appear within 10 days after all the constituents have been delivered.

We find that it is very important to properly record workshop proceedings in one, easily searchable place. Also, we want to contribute in this way to the growing acceptance of the view that all scientific publications should be freely available on-line.

We hope that researchers working in Theoretical Computer Science will follow the example of the many others in accord with the originators of this idea.  Please see http://published.eptcs.org/ for the list of published workshops.

The editors,

Rob van Glabbeek (NICTA, Sydney, Australia)
   Editor in Chief
Luca Aceto (Reykjavik University)
Rajeev Alur (University of Pennsylvania)
Krzysztof R. Apt (CWI and University of Amsterdam)
Lars Arge (Aarhus University)
Ran Canetti (Tel Aviv University)
Luca Cardelli (Microsoft Research)
Rocco De Nicola (Universita di Firenze)
Jose Luiz Fiadeiro (University of Leicester)
Wan Fokkink  (Vrije Universiteit Amsterdam)
Lane A. Hemaspaandra (University of Rochester)
Matthew Hennessy (Trinity College Dublin)
Bartek Klin (Warsaw University, University of Cambridge)
Evangelos Kranakis (Carleton University)
Shay Kutten (Technion)
Nancy Lynch (Massachusetts Institute of Technology)
Aart Middeldorp (University of Innsbruck)
Benjamin Pierce (University of Pennsylvania)
Gordon Plotkin (University of Edinburgh)
Vladimiro Sassone (University of Southampton)
Robert H. Sloan (University of Illinois at Chicago)
Wolfgang Thomas (RWTH Aachen University)
Irek Ulidowski (University of Leicester)
Dorothea Wagner (Universitaet Karlsruhe (TH))
Martin Wirsing (LMU Munich)
Moti Yung (Google Inc. and Columbia University)

Rolf Nevanlinna Prize to Daniel Spielman

Daniel Spielman  has been chosen for the 2010 Rolf Nevanlinna Prize for smoothed analysis of Linear Programming, algorithms for graph-based codes and applications of graph theory to Numerical Computing. The full details are here.


Congrats to Daniel for landing another prize after the Goedel prize 2008, which he received in Reykjavik during ICALP 2008.

Details about the other prize winners are here.

An interesting publication experiment in the logic-programming community

Krzysztof Apt has alerted me of the changes that have taken place in the Logic Programming community. The Association for Logic Programming (ALP) recently left the Springer LNCS series and embraced a new publication model for the proceedings of their flagship conference (the International Conference on Logic Programming (ICLP)) that tries to upgrade the papers directly to journal papers. Here is how the co-chairs of the 2010 edition of the conference describe the new publication model and its rationale.

The Logic Programming (LP) community, through the Association for Logic Programming (ALP) and its Executive Committee, decided to introduce for 2010 important changes in the way the main yearly results in LP and related areas are published. Whereas such results have appeared to date in standalone volumes of proceedings of the yearly International Conferences on Logic Programming (ICLP), and this method – fully in the tradition of Computer Science (CS) – has served the community well, it was felt that an effort needed to be made to achieve a higher level of compatibility with the publishing mechanisms of other fields outside CS.

In order to achieve this goal without giving up the traditional CS conference format a different model has been adopted starting in 2010 in which the yearly ICLP call for submissions takes the form of a joint call for a) full papers to be considered for publication in a special issue of the journal, and b) shorter technical communications to be considered for publication in a separate, standalone volume, with both kinds of papers being presented by their authors at the conference. Together, the journal special issue and the volume of short technical communications constitute the proceedings of ICLP.

The special issue of the journal  Theory and Practice of Logic Programming (TPLP) devoted to the 26th International Conference on Logic Programming Special is the first of a series of yearly special issues of that journal putting this new model into practice. It contains the papers accepted from those submitted as full papers (i.e., for TPLP) in the joint ICLP call for 2010. The collection of technical communications for 2010 will appear in turn as Volume 7 of the Leibniz International Proceedings in Informatics (LIPIcs) series, published on line through the Dagstuhl Research Online Publication Server (DROPS). Both sets of papers will be presented by their authors at the 26th ICLP.

This seems a very interesting way of dealing with some of the concerns that have been aired by some pundits about the publication culture within CS, while preserving the crucial role that conferences play in CS. I think that it is certainly worth a thought.

Call for papers: ICALP 2011

The first call for papers for ICALP 2011, which is presently being distributed at ICALP 2010, is here.

I hope that you will make plans to submit excellent papers to ICALP 2011.

Organizing a conference with satellite events

Suresh asked me to expand on a comment I posted here, where I described my experience with the organization of ICALP 2008 in Reykjavik, which I believe is still the most attended and event-packed ICALP conference on record.

First of all, even without satellite events, ICALP is a three-track conference, and has been so since 2005, though typically only two tracks are running in parallel at each point in time. At ICALP 2008, in addition we had 12 satellite events, including the DYNAMO training school for doctoral students. There were no tutorials, apart from the lectures at the PhD school, but we hosted a masterclass by Peter Winkler on mathematical puzzles, which I estimate was attended by well over 250 people, including local high-school teachers and students. Overall, nearly 500 people were registered for the main conference and/or the satellite events.

The workshops were held the day before ICALP or during the week-end following it. They were selected by the ICALP organizers amongst a fairly large number of proposals that we received in response to a call for workshops, based on their perceived scientific quality and on their potential interest to the ICALP community. As ICALP organizers, we made sure that each workshop had a suitable room at the university and some minimal amount of logistical and technical support. (Typically, at least a local student or a postdoc was permanently in residence during each workshop.) We also printed the preliminary proceedings of the workshops and took care of arranging lunches and coffee breaks. The costs were covered by the workshop registration fees. Overall, the overhead generated by the organization of the satellite events was minimal, or at least it looks so two years after the facts :-)

Organizing such a conference was not an easy job, but it was not as daunting as it may seem. In hindsight, I think that it was important to organize the event at the university (not a hotel---in passing, I very much prefer attending events held at universities rather than hotels), to have the assistance of the university support services, of some local students and postdocs, and of experienced conference organizers who took care of the registrations, of the lunches and coffee breaks and of the social programme. Magnus Halldorsson, Anna Ingolfsdottir and I organized ICALP and were assisted by Bjarni Haldorsson and MohammadReza Mousavi in the organization of the workshops. I firmly believe that the task of organizing a conference like ICALP should be shared amongst several people. This certainly worked for us and helped us work more cheerfully, and overcome personal problems, mishaps and periods of crisis and panic that arose during the year before the conference took place.

Overall, I do not think that organizing ICALP ended up being much more work than organizing a single-track conference without satellite events.

Let me close by adding that the model used for ICALP is rather common in conferences related to TCS with a "volume B flavour". See, for instance, the experience of the ETAPS conference series, which involves five major conferences, tutorials and a large number of satellite events, and of the Federated Logic Conference (FLoC), featuring eight major conferences and large number of workshops in 2010. Readers of this post may like to know that typically workshops are proposed by members of the community, and so are the tutorials at ETAPS.

As an external observer, I fail to see why STOC could not follow the example of those federated conferences and, at the same time, broaden its scope to cover more topics in TCS and accept a few more papers, if their quality is excellent, rather than relinquish its high-profile, peer-reviewed status.

Gödel Prize 2010

I have not seen any official announcement yet, but, according to Wikipedia and to Theory Announcements (thanks to the anonymous commenter who pointed out the latter source), the Gödel Prize 2010 has been awarded to Sanjeev Arora and Joe Mitchell for their concurrent discovery of a polynomial-time approximation scheme (PTAS) for the Euclidean Travelling Salesman Problem. Congrats to Arora and Mitchell!

Extended Deadlines for SOS 2010

I am co-chairing SOS 2010, an affiliated workshop of CONCUR 2010, which will be held in Paris. You are still on time to submit a paper to that event! The new submission deadlines are as follows:

• Submission of abstract: Friday 28th May 2010 Tuesday 1st June 2010 (strict)
  
• Submission: Wednesday 2nd June 2010 Monday 7th June 2010 (strict)

Can you resist the lure of Paris in late August-early September?

My Workplace

Here are some views of my workplace and its environment. The two photos above picture the entrance to my "professorial work area" :-) The one on the right depicts the entrance to my work area and its immediate environment, with the work places of Anna Ingólfsdóttir (left) and Magnús Halldórsson (right, behind the stand where we place some of our recent papers and books). This is the heart of our ICE-TCS enclave.

Can one work in such an environment? So far, the answer seems to be yes, but this is mainly because I am starting to believe one can work anywhere provided everyone in one's neighbourhood adheres to some basic ground rules.

Is the open-space environment conducive to academic work? This I am much less convinced about.

To conclude, here is what the open-space work environment looks like when I arrive at work in the morning. (The photo is taken from outside my cubicle.)

First Presburger Award to Mikolaj Bojanczyk

The Presburger Award Committee, consisting of S. Leonardi, A. Tarlecki, and W. Thomas (chair) has chosen Mikolaj Bojanczyk as the first recipient of the EATCS Presburger Award for young scientists.

The motivation from the award committee reads as follows:

Mikolaj Bojanczyk, 32 years old, has contributed numerous deep results to automata theory and to logic and algebra in computer science. Among them is the theorem stating that tree walking automata are strictly weaker than general tree automata, the definition of new decidable logics based on quantifiers for boundedness, and the development of a novel algebraic framework for the study of properties of unranked trees. His work thus led to the solution of long-standing open problems and introduced methods that open new directions in theoretical computer science (also relevant to neighbour disciplines such as data base theory). The committee recommends Mikolaj Bojanczyk as an exceptional young scientist who not only fully deserves the Presburger Award but is also an ideal first recipient. The committee also would like to mention that more than one excellent nomination was made, a fact which lets us hope that the Presburger Award will receive several nominations of truly exceptional level from all areas of theoretical computer science in the coming years.

Let me add that, in 2005, Mikolaj's doctoral thesis, entitled ”Decidable Properties of Tree Languages”, received the Ackermann award of the European Association of Computer Science Logic. In 2006, he was awarded the ”Witold Lipski prize for young Polish researchers in computer science”. In 2007, he received the Kuratowski award for young Polish mathematicians, awarded by the Polish Mathematical Society. In 2009, Mikolaj became one of the very few young computer scientists to obtain a European Research Council Starting Grant.

Congrats to Mikolaj for yet another well-deserved award. May his work go from strength to strength.

Fifth International Summer School on Rewriting

The 5th International School on Rewriting will be held in the period  July 3-8, 2010, in Utrecht, The Netherlands. The programme includes both basic and advanced lectures. Perhaps some of your graduate students will be interested in attending the event.



Term rewriting is a core area in Theoretical Computer Science. It is powerful model of computation underlying much of declarative programming, which is heavily used in symbolic computation in logic and computer science. Applications can be found in theorem proving and protocol verification, but also in fields as diverse as mathematics, philosophy and biology.

     

School of Computer Science at RU on Twitter

The School of Computer Science at Reykjavik University, where I work, has made the step to advertise its events and news on Twitter. See here. Our aim is to make potential students and the community at large aware of what the school can offer.

Does your institution have a Twitter page too? Do you think that Twitter is a good channel for spreading news to potential CS students?

ICE-TCS Logo

After five years of operation, ICE-TCS (our little research centre in TCS) finally has a logo, which you see displayed above in its full glory. The logo design is courtesy of Emilka Bojańczyk. Do have a look at her graphic design work, which I like a lot. If you need logos, posters or any other kind of TCS- or Maths-related  design work, I strongly recommend Emilka.

Apart from being a professional graphic designer, Emilka has a mathematical background (she graduated with honours from the Mathematics Department of Warsaw University in 2002) as well as strong family connections with TCS :-) She has also designed the logo for the STACS conference series, amongst other things.

Thanks Emilka!

LICS 2010 Test-of-time Award Winners

I just read an email announcing the papers selected for the 2010 LICS Test-of-Time Award. For the 2010 LICS Test-of-Time Award, all papers from LICS 1990 were considered by an Awards Committee consisting of Glynn Winskel (chair), Jean-Pierre Jouannaud and John Mitchell.

In view of the weight of highly-influential papers, across a range of areas, the committee has taken the exceptional step of selecting four papers! They are:

• Model-checking for real-time systems by R. Alur, C. Courcoubetis and D. Dill. This paper was a pioneer in the model checking of real-time systems. It provided a polynomial-space algorithm for the model checking of a real-time logic (an extension of CTL with timing constraints) with respect to a continuous-time model. Its techniques are still used extensively and results of this paper form part of almost any course or tutorial on real-time verification.
• Symbolic model checking: 10^20 states and beyond by JR Burch, EM Clarke, KL McMillan, DL Dill and LJ Hwang. This paper revolutionized model checking. Through its symbolic representation of the state space using Randy Bryant's Binary Decision Diagrams (BDDs) and its careful analysis of several forms of model checking problems, backed up by empirical results, it provided a first convincing attack on the verification of large-state systems. The paper was a major agent in establishing BDDs as a tool in mainstream computer science.
• The theory of ground rewrite systems is decidable by M Dauchet and S Tison. This paper asked what has proved to be a very important question, whether the first-order theory of one-step rewriting is decidable. The paper settled the question positively for the theory of ground rewrite systems using innovative techniques on tree automata. Its techniques rekindled an interest in automata theory on finite trees, now a major topic, with many current applications from rewriting through to security, program analysis and concurrency.
• Recursive types reduced to inductive types by P Freyd. This paper showed what was really going on with the classic method of solving domain equations.  By separating positive and negative occurrences of the unknown in a domain equation, it gave an elegant category-theoretic treatment of recursively defined domains that extends the well-understood and widely-used methods of initial-algebra semantics. Its methods are now standard. They led to new techniques for relating operational and denotational semantics, and new mixed induction/coinduction principles.

Congratulations to all the recipients of the awards!

Typos, typos....

I always tell my students at all levels that there is no excuse for not spell checking one's writings. There are rather good spell-checking programs out there, and one should use them to spot obvious typos.

Spell-checking programs, however, are no substitute for careful proof reading of one's papers. I was reminded of this fact of professional life some time ago when, while reading the revision of a journal submission of mine, I spotted the mention of a "format for impotence of operators" (in lieu of "format for idempotence of operators"). It would have been embarrassing, but admittedly amusing, to send the paper off with that typo left unspotted, just as it was entertaining for my students to attend a lecture mentioning a "poof technique" (rather than "proof technique") on a slide :-)

No spell-checker can find those typos. I'll use them to motivate my students to proof read their texts with care.

ICALP 2010: Accepted papers

The list of accepted papers for ICALP 2010 is out. Based on what I saw as a PC member for track B, the overall quality of the submissions was, in general, very high and many good papers could not be selected for presentation at the conference.

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.