Friday, November 21, 2008

Report on the Innovative Teaching Day at Reykjavik University held on 14 August 2008

These notes have been lying in my folders since last August. I am posting them here just in case they may be of interest to some of my two readers, with apologies for the low-tech embedding of URLs in the running text.

On 14 August 2008, Reykjavik University held one of its Innovative Teaching Days for 2008. The programme featured two invited presentations by two academics from MIT: Janet Rankin (, associate director for teaching initiatives at the Teaching and Learning Lab at MIT (, and Donald Sadoway (, who is John F. Elliott Professor of Materials Chemistry at MIT and is known as a star teacher within that institution. Overall, the establishment and the level of activity of the Teaching and Learning Lab at MIT indicate how important quality teaching is considered by that top-notch university.

The first presentation was delivered by Janet Rankin, who started by asking the question:

"What do we know about student learning and how can it inform our teaching?"

Janet Ranking stressed that every course/lecture must have a road map (a clear outline) and well defined objectives (clear results). She also said that the increasing impact of cognitive learning theories on teaching is producing a shift towards student-centred, active learning.

Message 1: When teaching try to raise the students' awareness of themselves as learners.

Message 2: When planning a course and each of its components, consider the learning objectives for your students.

Ask yourself: "What promotes learning by the students?" Typical answers are:
It is also important "to teach for transfer", i.e., teach students in such a way that they can apply what they have learned in one class in another. This can be achieved by teaching in a variety of contexts and by providing students as many examples of applications as possible. One should try to use a varied collection of examples to clarify concepts, and it is advantageous to provide examples from different disciplines. Keep always in mind that learning is context dependent.

Involve the students in peer instruction. This involves making them solve problems, listen critically to solutions by their peers, evaluate the solutions, and argue about their appropriateness.

A useful tip: After each lecture/session make the student write down on a card the most confusing aspect of the meeting. Use the answers to reflect on what you can do to improve.

See this booklet for more information: Janet Rankin also recommended this book.

The second talk of the day was delivered by Donald Sadoway, who has been professor at MIT since 1992. (Personal comment: For what it's worth I have to say that this was one of the most entertaining presentations about any topic I have heard in my career. I have no doubt that he is indeed the star teacher the announcement claimed he was and that students flock to his classes in large numbers.)

Donald Sadoway's mission in teaching is to invigorate engineering education because it is typically boring! He stated right at the beginning that we need to make universities a better environment for teachers. We need to give our students the foundations that they will need to be successful in our future world that will be dominated by bio, nano and info sciences. (Ask yourself: How much of these foundational sciences do our students see in our degree courses right now?)

As a running example, Donald Sadoway mentioned his experience with the course 3.091 at MIT. This course
  • lays the foundation for more chemistry,
  • prepares students for their majors, and
  • provides scientific and technical literacy.
For many students, this is the only chemistry course they will take. Before he took over, this was a troublesome course. Now, there are 600 students taking it on average. His approach in planning the course can be summarized as follows.
  • When planning a course, begin with a clean slate. If you start by looking at what was there before or at a typical book, you will soon realize that there is too much material to be covered.
  • Less is actually better!
  • When selecting the material to be covered in the course, divide it into three categories (of decreasing order of importance):
    • What should the students recall from the course on their death bed?
    • What knowledge would be useful, but is not vital?
    • And what would be knowledge from the course they might recite at a cocktail party to show they have some advanced knowledge?

To evaluate student performance in the course and keep track of student progress, Donald Sadoway uses weekly 10-minute quizzes, monthly tests (with one A4 aid sheet) and a final exam, which he calls a celebration for final festival. The final celebration gives the student time to reflect on what they have learned and is an extra opportunity for improving their learning skills and mastery of the material. The final celebration should be a suitably challenging learning experience since, as Sadoway put it, "no pressure, no diamonds".

Each concept in the course is illustrated by suitable examples providing context. (See above.) Sadoway always offers references to history of science, music, arts and whatever else provides context and makes the material entertaining and catchy. He also uses parts of the lectures to touch upon the theme "chemistry and the world around us".

Note that the course has no laboratory component since there is no lab that can hold 600 students. To address this "shortcoming", Sadoway asked himself: "So, what is important?" The answer he came up with is:
  • Ethics,
  • Data analysis,
  • Communication, and
  • Teamwork.
The result was the development of a virtual lab. There is not need of physical contact during the "lab classes".

He encourages students to read the classics, and use that the university or departmental library to go back to the articles that shaped our understanding of a field. He also runs themes within a course. Examples of such themes are:
  • Women in science (studies of abuse),
  • History, society and solid state chemistry (he proposed a course on this topic, but his proposal died because the faculty of history did not want to give students credits for the course since it was taught by an engineer and was considered an engineering class).
His firm belief in making students go to the primary sources led him to develop the course "3.093 Information Exploration: Becoming a Savvy Scholar". See

He said that he has reached the following conclusion:

"I'll do anything I want in that lecture room provided it is in good taste."

After all, if I may quote him again,

"Tenure means never say 'I am sorry'."

Sadoway said that a good university education should give our students a methodology for developing solutions to problems. On the other had, a great university education should provide them with a methodology for developing methodologies!

You can hear Sadoway present this course on YouTube at

and you can watch him deliver his first lecture in the course at

You can also read about Sadoway's involvement in the "Picturing to Learn" programme at MIT at

More on the programme is available at


I encourage you to look at the short movie "Teaching Teaching & Understanding Understanding" conceived and directed by my Danish colleague Claus Brabrand. Info on the movie, which describes John Biggs' constructive alignment, is available at When I had a brief stint as head of the Computer Science Department at RU, I ordered 20 copies of the DVD and encouraged my colleagues to watch it and pay heed to its message. I encourage your to buy a copy of the DVD, which can also be viewed on YouTube in low quality format.

Aalborg University is a world leader in problem-based learning. You can read about problem-based learning at Aalborg University, with special emphasis on its implementation in engineering education, at Information on the European Consortium of Innovative Universities, of which Aalborg is a member, is at

Monday, November 17, 2008

Call for Nominations: Gödel Prize 2009

The Call for Nominations for the 2009 Gödel Prize has been posted (see this pdf file). Nominations for the award should be submitted to the Award Committee Chair, Shafi Goldwasser. The deadline for nominations is January 31st, 2009.

Do nominate your favourite papers, and recall that any research paper, or series of papers, by a single author or by a team of authors is deemed eligible if the paper was published in a recognized refereed journal before the nomination, but the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 1995.

Friday, November 14, 2008

Italian Academics On Strike Today

As I write, many Italian academics and university students are gathered in Rome to protest against the cuts to the Italian university system proposed by the Italian government. (The estimate is that 100,000 people will take part in the protest, despite the rainy weather.) See, e.g., here and here for accounts of the developments leading to the strike in English. A live report (in Italian) can be found here. (The protesters have been quite creative, as the banner on this photo indicates. The text on the banner can roughly be translated thus: "Berlusconi, research is the only reason why you still have hair." :-))

I wish my colleagues in Italy the best of luck in their protests. It is high time that Italian governments of all denominations understand that cutting on education and research is the surest recipe for offering a bleak future to my country.

However, I often feel that Italian academia has done itself no favours by contributing to the creation of a system that is highly self-referential and insular. (Italy imports very few students, researchers and lecturers from abroad, and the word "abroad" can often truthfully be interpreted as meaning "coming from a different institution.") The average Italian seems to believe that Italian academia is tainted by scandals, nepotism, the so-called "baronie", and that Italian academics are lazy people who only collect their salaries while producing bad teaching and little or no research. They are not aware of the existence of a large community of highly dedicated, motivated and capable academics who sweat blood to reach peaks of excellence within a system that works against them, rather than for them, and with low salaries. Excellence is often not nurtured in my home country, alas.

It is time for decisive action, I feel. Italian academia needs to regain the trust of the Italian people and give hope to the many young Italian researchers who see no future for them in science. Get independent panels of top-class, expert international evaluators to evaluate all the departments and universities in Italy both in teaching and research. The result of such an evaluation should be used to allocate a sizable share, say 30-40%, of the funding to the departments and universities. Only then, I believe, we will see scientific merit taking centre stage in the evaluation of applicants for positions and a leaner hiring system that will offer Italy's young scientists regular job opportunities.

Of course, the evaluation should be repeated at regular intervals.

Addendum: People interested in assessments might find it worthwhile to read the document
Education at a Glance 2008 OECD Briefing Note For Italy.

Monday, November 10, 2008

The Complexity Of Deciding Bisimilarity Over Finite Labelled Transition Systems

A fairly classic result from the concurrency-theory literature with a complexity-theoretic flavour is a theorem by José L. Balcázar, Joaquim Gabarró and Miklos Santha to the effect that checking various forms of bisimilarity (viz., strong, weak (aka observational equivalence) and rooted weak bisimilarity (aka observational congruence)) over finite labelled transition systems is P-complete. This theorem holds true even over acyclic labelled transition systems over a one-letter alphabet.

The original journal paper appeared in Formal Aspects of Computing in 1992. (See here for the BiBTeX reference. I am not aware of a version of it that is available on line.) It is one of those papers that I have been citing for a while, but whose result I had never studied in great detail despite meaning to do so.

At long last, I pulled myself together, read the fine print of the paper, and, jointly with Anna Ingolfsdottir, decided to pen down a write-up of the ideas in the proof of the main result in that work. We made the piece available from the web page for our book as supplementary reading material; see Deciding Bisimilarity over Finite Labelled Transition Systems is P-complete.

The note is written in the same pedagogical style as the textbook it accompanies, and we plan to reuse it as part of an ongoing project we expect to complete by the end of the year. We trust that it is suitable for classroom use as well as for self study, and we hope that it will make another classic result from concurrency theory accessible to mature BSc and MSc students.

Wednesday, November 05, 2008

EATCS Award 2009: Call for Nominations

The official call for nominations for the EATCS award for 2009 is now available. (See here.) The call will also appear in the October edition of the Bulletin of the EATCS, and on the web site of the EATCS.

The EATCS Award is awarded in recognition of a distinguished career in theoretical computer science.

Please publicize the call for nominations amongst your colleagues and within your institution, and consider sending a nomination yourself. There are many worthy candidates for the prize within our community, but they need to be nominated by someone :-)

Wednesday, October 22, 2008

Extended Deadlines for FSEN 2009

I have been asked to announce that the deadlines for submission to FSEN 2009 have been extended.

The revised deadlines are as follows.

Abstract Submission: November 3, 2008
Paper Submission: November 10, 2008

The conference is held in what looks like a beautiful location in the Persian Gulf, and features top-class invited speakers.

Do consider submitting one of your papers.

Monday, October 06, 2008

New Centre of Excellence in Denmark

I recently learnt about the existence of a new centre of excellence in Denmark, the MT-Lab, devoted to topics close to my research area. The centre will officially open its activities in the second half of November.

Anna and I know basically all the consortium members very well, and it would take another post to describe our connections with several of them. These scientists are at the forefront of their research areas in computer science and control theory, and have been collecting centre-of-excellence funding from Danish governmental funding bodies before and on a regular basis. I have no doubt that the MT-Lab will become one of the most successful research centres in the world in its fields of expertise, and I am looking forward to monitoring its progress. Congratulations to the consortium members for the establishment of the centre!

A very interesting aspect of this centre of excellence is that this time around the 25 million DKK funding it (roughly € 3.35 million) are being provided by a private foundation, The Villum Kann Rasmussen Foundation. (See also this page to find out what other things they fund.)The existence of such foundations is one of the (many) strengths in the Danish funding for basic research, and I do not find it at all surprising that Denmark is home to a good collection of centres of excellence with very good international visibility and impact. With centres of this calibre, it is easy for Denmark to attract top-class scientists from abroad and to entice them to relocate to a country with good resources, a top-class welfare state and an excellent quality of life overall. (Yes, one pays very high taxes in Denmark, but, at times like the ones we are living, the sense of security that a well-oiled welfare state gives one becomes even more important than ever before.)

The Danish model for research funding has also inspired recent developments in the funding schemes available at European level. Let's see how much of this will survive the present turmoil on the financial markets.

Thursday, September 25, 2008

Vardi Receives The Blaise Pascal Medal in Computer Science For 2008

I just learned that Moshe Vardi is the recipient of the Blaise Pascal Medal in Computer Science for 2008 of the European Academy of Sciences. This is outstanding news for TCS as a whole and for the logic in computer science community in particular.

The motivation for the prize reads:

In recognition of his outstanding contributions in several areas of computer science connected by their use of logic as an underlying methodology. His work has had fundamental and lasting impact on automatic verification, logic of knowledge, database theory, and finite-model theory.

Moshe also contributes to the development of activities in TCS in my small corner of the world by sitting on the advisory board of ICE-TCS.

Congrats to Moshe! Somehow I feel that there will be more and even more prestigious awards in store for him.

Monday, September 15, 2008

Concurrency column for the October issue of the BEATCS

I just posted the instalment of the concurrency column for the October issue of the Bulletin of the EATCS. The article, entitled Formalizing operational semantic specifications in logic, has been contributed by Dale Miller.

I strongly recommend this article not only to the standard readership of the concurrency column, but also to those readers who normally focus on logic in computer science and on programming languages amongst others. By publishing it, I feel like I am killing at least three birds with a stone.


Wednesday, September 10, 2008

TCS 2008: Take Two

I am attending the session before lunch of TCS 2008, after which I will go to Milan central station to catch a train back to Pescara, my home town.

Today's invited talks were delivered by two Italian computer scientists, Antonio Restivo and Luca Cardelli.

Over the last 35 years or so, Restivo has been one of the prime movers in the Italian community of researchers working on automata and formal language theory. In his talk, he addressed the following basic question:

What is the "right" way of extending the notion of recognizability from word languages to picture languages?

He described the approach he has developed with his co-workers, which is based on the notions of locality and projection. This notion turns out to coincide with the class of picture languages that are definable using existential monadic second-order logic. This leads Restivo to believe that it is the "right" notion of recognizable 2D language.

The notion of recognizable 2D language offers some surprises, at least for a non-expert like me. For instance, the language consisting of the square pictures over alphabet {a,b} that contain an equal number of a's and b's is recognizable, and so is the language of pictures of a's whose sides have prime length.

Luca Cardelli needs no introduction. In his talk, which was based on this paper, Luca presented a basic process-algebraic language that can be used to describe the ordinary differential equations that one meets in (bio-)chemistry. He showe several interesting applications of this language and how it can be used to investigate the discrete vs. continuous modelling dichotomy. The talk was excellent, as usual, and I am sure that the slides will appear very soon on this web page. It was great to see that a simple process calculus based on a stochastic version of Milner's CCS can be used to specify ODEs in a compositional way. For TCS people like us, the automata described by terms in the language "explain" the ODEs and why they take they form they take. Luca also showed us that his compilation of terms into ODEs produces exactly the known ODEs for some classic examples, such as the predator-prey one.

Yesterday, Tim Roughgarden gave a very interesting and beautifully delivered invited talk entitled Algorithmic Game Theory: Some Greatest Hits and Future Directions. You can read the paper here.

Tuesday, September 09, 2008

TCS 2008: Invited Speakers for the First Day

I am in Milan for TCS 2008, the bi-annual conference organized by IFIP TC1 in conjunction with the World Computer Congress (WCC). TCS 2008 aims at covering both volume A and volume B TCS, and this year features as many as seven 45-minute invited talks over three days. (IMHO, this is an exceptional number of invited talks for such a short conference.)

Being part of an event like the WCC, which features many events for IT professionals, makes TCS a very expensive TCS conference to attend, and the atmosphere is somewhat different from that of the typical conference TCS folks tend to attend. The early registration fee for an IFIP member was 525 euros (the late one is 680 euros for IFIP members and 800 euros for non-members), it does not include lunches and at the coffee breaks we get just coffee! Not surprisingly attendance at the conference is small and, despite the number of CS departments in Milan and surrounding areas, there are preciously few locals taking part in the event. I guess that there is a definite lesson to be learnt here.

Here I will limit myself to discussing some of the invited talks at the conference. TCS 2008 was kicked off by a presentation delivered by Grzegorz Rozenberg entitled Natural Computing. In his talk, he discussed models of computation inspired by nature and how they differ from classical computational models we use in computer science. I have not found his presentation on line, but you can read Rozenberg's views on the subject of natural computing vis-a-vis classical computer science in his acceptance speech for a honorary degree he received from the University of Bologna as well as in the many (and I really mean "many") technical papers he has written on the topic.

Rozenberg's invited talk was followed by a truly remarkable presentation by Javier Esparza. Javier was one of our invited speakers at ICALP 2008 and I already sang the praises for his presentation in Reykjavík. I really wish that more students had been there to see how to deliver an excellent talk despite a lack of slides for the first ten minutes or so because of technical problems. This was an example of how very good story-telling skills can easily overcome technological failures (at least at the beginning of a technical talk). After all, a conference speaker or a teacher are not so different from ancient story tellers, minstrels or gurus.

Javier's talk reported on results that he has obtained with his students on the solution of monotonic polynomial equations, a subject that one would expect to have been completely settled by mathematicians a long time ago, and that instead has been the source of interesting recent developments in the computer-science literature. The key point here is that one can obtain very strong results on methods for solving polynomial fixed-point equations if one restricts oneself to monotonic equations. I let you browse through Javier's slides since nothing I could write here would do justice to the many exciting results he has achieved with his students. The slide also list some interesting open problems. In particular, consider the problem

MSPE-DECISION: Given an MSPE X = f (X) with rational coefficients and k rational, decide whether the first component of the least solution of that system of monotonic polynomial equations is at most k.

The above problem is in PSPACE and unlikely to be in P. It might be solvable using a polynomial number of arithmetic operations. According to Javier, a proof of this fact would be a sensational result. Some of you might like to sharpen their pencils and try to solve this problem.

I was again pleased to be in the room to listen to yet another inspiring talk by Javier, who is rapidly becoming one of the favourite invited speakers at European TCS conferences.

I will try to report on the other invited talks I heard at some point soon.

Monday, September 01, 2008

Bereavement in Italian Theoretical Computer Science

On the night between August 19 and August 20, Italian TCS prematurely lost Stefano Varricchio (University of Rome "Tor Vergata") while he was on holiday with his family. He was 48, or so I am told.

Stefano's research was in the classic areas combinatorics on words, automata theory and formal languages. I am not qualified to offer an assessment of his research contributions, and I hope that some of my readers who work on the aforementioned topics will post comments on Varricchio's work. I met him once a few years ago during a visit to the University of L'Aquila, where he was a full professor at the time. I recall that, after my presentation based on this paper, he kindly pointed out the relevance of a famous theorem by Fine and Wilf for some of the results I presented.

Here is the theorem.

Theorem (Fine and Wilf, 1965) If a word x has periods p and q, and has length at least p + q − gcd(p, q), then x has also a period gcd(p, q).

A relative of mine and his wife, who followed Stefano's compilers course in L'Aquila, told me that he was one of the best teachers they had during their studies.

To quote a poem by Giuseppe Ungaretti,
Si sta come, d'autunno, sugli alberi, le foglie.
G. Ungaretti - Soldati Bosco di Courton luglio 1918

Tuesday, July 29, 2008

Desperately Seeking Mathematical Truth

The August issue of the Notices of the AMS includes an opinion piece entitled "Desperately Seeking Mathematical Truth" by Melvyn B. Nathanson. At the risk of oversimplifying the message in that opinion piece, the gist of the article can be summarized as follows, using direct quotes from Nathanson's opinion piece.
  • "Our knowledge of the truth of a theorem depends on the correctness of its proof and on the correctness of all of the theorems used in its proof. It is a shaky foundation" because "many great and important theorems don’t actually have proofs. They have sketches of proofs, outlines of arguments, hints and intuitions that were obvious to the author (at least, at the time of writing) and that, hopefully, are understood and believed by some part of the mathematical community."
  • Recognizing mathematical truth is harder than one might think at first. "If a theorem
    has a short complete proof, we can check it. But if the proof is deep, difficult, and already fills 100 journal pages, if no one has the time and energy to fill in the details, if a “complete” proof would be 100,000 pages long, then we rely on the judgments of the bosses in the field. In mathematics, a theorem is true, or it’s not a theorem. But even in mathematics, truth can be political."
So, mathematical truth is the result of a social process. (I'd rather not say "political".) A theorem is proven when a sufficient portion of the mathematical community agrees that its proof is convincing and starts building on it, despite the absence of a "complete" proof. I do not find this a particularly controversial or novel opinion, and I am sure that it has been aired before. What I find utterly remarkable is the apparent robustness of the notion of mathematical truth that arises from the aforementioned social process.

Yes, proofs of several published theorems contain mistakes. However, more often than not, the mistakes can be fixed and the results turn out to live to see the day after all.

Of course, I expect that mathematicians will want to improve upon the social notion of proof that underlies their profession. Quoting again from the opinion piece by Nathanson:

We mathematicians like to talk about the “reliability” of our literature, but it is, in fact, unreliable.

Part of the problem is refereeing. Many (I think most) papers in most refereed journals are not refereed. There is a presumptive referee who looks at the paper, reads the introduction and the statements of the results, glances at the proofs, and, if everything seems okay, recommends publication. Some referees do check proofs line-by-line, but many do not. When I read a journal article, I often find mistakes. Whether I can fix them is irrelevant. The literature is unreliable.
How can the reliability of mathematical proofs be improved? When should a proof be deemed to be "complete"? As a computer scientist, I'd say that a proof is really "complete" when it can be verified by a computer-based proof checker and it has been independently verified using a few such software tools. I know that this is a very stringent requirement, which will most likely never be implemented, but either we are ready to accept that mathematical truth is an unreliable but remarkably robust notion or we enlist the help of our computers to try and make it more reliable.

Do any of you think that proof-checking of research-level mathematical proofs will become commonplace in our lifetime?

Addendum dated 5 August 2008: I should have known that Doron Zeilberger would have commented on Nathanson's opinion piece. Of course, Dr. Z's opinion is thought provoking as usual. You can read it here. In summary, Dr. Z suggests two ways for improving the reliability of mathematical knowledge.
  1. In his words, "First computerize! Computers are much more reliable than humans, and as more and more mathematics is becoming amenable to computer checking, this is the way to go."
  2. Abandon anonymous refereeing.
I have already expressed support for the first suggestion in my original post, as have some commentators in their very thoughtful comments. (I really appreciated them, and I hope to reply to them soon.)

Regarding the second suggestion, I am not so sure that abandoning anonymity in refereeing would have such a great effect on the reliability of mathematical literature. The bottom line is that one should exercise the greatest amount of professionalism in all aspects of the academic profession, regardless of whether one does something anonymously or not. Excellent referees are a great resource to have, and editors and PC members soon build a trusted core of referees that can be relied upon to provide high-quality feedback to authors and editors alike. Referees who do not do a good job tend to be ignored after a while, as do editors who act as black holes for the papers that are submitted to them.

Wednesday, July 23, 2008

Third ICE-TCS Annual Report

The third ICE-TCS annual report has been available since June 12, but I never mentioned its availability on this blog. If you are interested in keeping abreast of what is happening in our little TCS centre here in Reykjavík, do have a look.

Some of the people who attended ICALP 2008 asked us what we are going to do with the centre when funding runs out. Our answer was, "What funding?" The centre operates with very few resources and without specific funding to support its activities. We try to raise money in ad hoc and haphazard ways.

The Icelandic Fund for Research announced the availability of centre-building funding for the first time ever last spring. A consortium led by ICE-TCS sent in a pre-proposal, but our expression of interest was not one of the ten that were selected for further consideration, alas. Such is life, I guess, but, if I may say so, the list of ten selected pre-proposals is somewhat surprising on purely scientific grounds and hardly fulfils the requirements concerning international collaboration. (Our pre-proposal had BRICS, CISS, FUNDIM and the Centre for Computational Molecular Biology at Brown University as some of its cooperating centres.)

Anyway, we will try to maintain a decent level of activity in TCS on this remote, but rather attractive, island in the north Atlantic :-) For present activity on another much smaller, but also much hotter, island, see Luca Trevisan's in theory.

Monday, July 21, 2008

General Assembly of the EATCS at ICALP 2008

The EATCS holds its annual General Assembly (GA) during ICALP. This year's GA was held during ICALP 2008 on Tuesday, 8 July, after Peter Winkler's master class on mathematical puzzles. I have already covered some of the highlights of the GA in earlier posts (e.g., the best paper awards for ICALP 2008 and the proposed new young research prize in TCS). Here I will limit myself to highlighting a few of the many issues under discussion within the EATCS Council that you might be interested in commenting on. In general, the EATCS strongly encourages feedback and suggestions from the members of the TCS community at large. I will pass on to the Council any suggestion/comment/criticism you might have.

First of all, here are some statistics presented by Leslie Ann Goldberg regarding track A of ICALP 2008. Track A had 133 submissions that could be classified as dealing with Design and Analysis of Algorithms, 87 for Complexity Theory and 67 under the heading Approximation. The most successful topic as far as percentage of acceptances was concerned was Quantum Computation (6 selected out of 14 submissions, 43% selection rate); Randomness was second with 15 selected out of 39 submissions (38% selection rate). Overall, Germany, Israel and the USA contributed 120 submissions to track A.

For track B, there were 8 selected papers under the heading Verification, 7 on Words and Trees and 6 on Logic and Complexity. Germany and France led the number of authors with 39 and 39 authors each. The UK, the USA and Italy were next in line with 32, 29 and 25 authors, respectively. Spain was next with 13 authors.

No comparable statistics were presented for track C. However, Ivan Damgaard remarked that it was noteworthy that no accepted paper for track C dealt with the formal specification and verification of security protocols.

The General Assembly approved the suggestion of the Council that ICALP 2010 be organized in Bordeaux, France. Igor Walukiewicz presented the bid from Bordeaux, highlighting many reasons for having ICALP there. The GA also discussed possible alternatives for ICALP 2011. In particular, Giorgio Ausiello mentioned that the sister society AAAC (Asian Association for Algorithms and Computation) has invited ICALP to Japan. Concerning 2012, Giorgio Ausiello mentioned that, in the occasion of the centennial of Turing's birth, a special event should take place in Cambridge, UK. The EATCS is considering the co-location of ICALP 2012 with the events in the Turing centennial.

Jan van Leeuwen reported on possible connections netween the EATCS and Computability in Europe, a new association that "aims to widen understanding and appreciation of the importance of the concepts and techniques of computability theory, and to support the development of a vibrant multi-disciplinary community of researchers focused on computability-related topics."

The EATCS Council has formed a new publication committee which I have been asked to chair. Apart from me, the committee will consist of Josep Diaz, Juhani Karhumaki, Burkhard Monien, Catuscia Palamidessi, Valdimiro Sassone and Maria Serna (the new editor of the Bulletin of the EATCS). One of the important roles that this committee will have is to propose future developments for the Bulletin, which is the flagship publication of the EATCS. I would be very happy to hear your opinions on and wishes for the BEATCS.

Amongst the many developments within the EATCS let me finish by mentioning that the EATCS Council has decided that the Secretarial Office will move to CTI. The Secretarial support will be partly paid by EATCS, partly sponsored by CTI. The experiment will be carried on for a period of three years. An important role that the new Secretarial Office will play is in maintaining an ongoing connection between the EATCS and its members. The latest membership figures show a worrying decrease in the number of members at a time when the EATCS needs the support of the TCS community to foster its increasing number of high-profile activities. The number of members of the EATCS has gone down from 1036 in 2006 to 882 in 2007, and has hit an all-time low in 2008 (with 678 members). I hope that the success of ICALP 2008 will help the association a little.

Many photos from ICALP 2008 are available by following the links from this web page.

Friday, July 18, 2008

CadiaPlayer Strikes Again

About one year ago, CADIAPlayer, developed by Yngvi Björnsson and his MSc student Hilmar Finsson within CADIA, our centre for AI research won the General Game Playing (GPP) competition at AAAI 2007. (The aim of the GGP competitions is to help develop systems that can accept a formal description of an arbitrary game and, without further human interaction, can play the game effectively.)

I am happy to report that, in a repeat of last year's final, CadiaPlayer confirmed its world-champion status in GGP at AAAI 2008 in Chicago by defeating ClunePlayer from the University of California, Los Angeles. (ClunePlayer has now been runner-up for three years in a row, and was the world champion in 2005.)

This is great news for the School of Computer Science at Reykjavík University. Congrats to Yngvi, Hilmar and Gylfi.

Wednesday, July 16, 2008

June Issue of the Bulletin of the EATCS

Continuing the open access policy of the EATCS, the June issue of the BEATCS is now available here for free download. I trust that you will find something of interest to you in this volume, which also features a little technical contribution by your truly.

Let me take this opportunity to encourage all of you to become members of the EATCS. Becoming a member is cheap (30 €) and easy. Moreover, by becoming a member you will support the activities of the TCS community at large not just in Europe, but across the world. These are busy times for the EATCS, and the organization needs your support to thrive.

For instance, I can tell you that, during its meeting at ICALP 2008 in Reykjavík, the EATCS Council decided to create a new Award for Young Researchers. The new award committee of the EATCS will soon define the details for the prize. The EATCS aims at having the rules set by ICALP 2009, so that after that conference, it can distribute the call for nominations, appoint the evaluation committee and set the deadlines with the aim to deliver the award for the first time at ICALP 2010. More news on the EATCS General Assembly held at ICALP 2008 will follow soon.

Some Recent Awards

A few awards and prizes have recently been handed out to members of the TCS community.

The LICS test-of-time award 2008 has been given to Martín Abadi and Leslie Lamport for their paper The Existence of Refinement Mappings. In Lamport's own words:

The method of proving that one specification implements another by using a refinement mapping was well-established by the mid-80s. ..... It was known that constructing the refinement mapping might require adding history variables to the implementation. Indeed, Lam and Shankar essentially constructed all their refinement mappings with history variables. Jim Saxe discovered a simple example showing that history variables weren't enough. To handle that example, he devised a more complicated refinement-mapping rule. I realized that I could eliminate that complicated rule, and use ordinary refinement, by introducing a new kind of dummy variable that I called a prophecy variable. A prophecy variable is very much like a history variable, except it predicts the future instead of remembering the past. (Nancy Lynch later rediscovered Saxe's rule and used it to "simplify" refinement proofs by eliminating prophecy variables.) I then remembered a problematic example by Herlihy and Wing in their classic paper Linearizability: A Correctness Condition for Concurrent Objects that could be handled with prophecy variables.

This paper was my first collaboration with Abadi. Here's my recollection of how it was written. I had a hunch that history and prophecy variables were all one needed. Abadi had recently joined SRC, and this seemed like a fine opportunity to interest him in the things I was working on. So I described my hunch to him and suggested that he look into proving it. He came back in a few weeks with the results described in the paper. My hunch was right, except that there were hypotheses needed that I hadn't suspected. Abadi, however, recalls my having had a clearer picture of the final theorem, and that we worked out some of the details together when writing the final proof.

I had just developed the structured proof style described in [100], so I insisted that we write our proofs in this style, which meant rewriting Abadi's original proofs. In the process, we discovered a number of minor errors in the proofs, but no errors in the results.

The first CAV award has just been given to Rajeev Alur and David Dill for the invention of the formalism of timed automata. See the full announcement for more details. This is a well deserved recognition to Rajeev and David for a fundamental contribution to the theory of real-time systems verification. Timed automata have been the subject of extensive theoretical investigation since the original paper by Rajeev and David and form the basis for software tools for the specification and verification of real-time systems such as Uppaal. Readers who are interested in a leisurely introduction to the basic theory of timed automata might wish to read part II of this book.

Finally, the European Mathematical Society (EMS) awarded its prizes at the 5th European Congress of Mathematics, held this week in Amsterdam (The Netherlands). The EMS prizes are awarded to young researchers not older than 35 years, in recognition of distinguished contributions in mathematics, and are presented every four years at the European Congress of Mathematics. One of the recipients of the EMS prizes is Assaf Naor, who is honoured for "his groundbreaking contributions to functional analysis, the theory of algorithms, and combinatorics".

Congrats to the award recipients!

Sunday, July 13, 2008

Leslie Valiant's EATCS Award Talk

An anonymous comment to my previous post on ICALP 2008 asked
I'm very curious what Valiant talked about Evolution, Intelligence and Human Brain. In particular if he said anything concrete.
Here are some recollections I have from Leslie Valiant's talk. I apologize if I have misinterpreted the main messages from his presentation.

Leslie started his talk by recalling that the first conference he ever attended was ALP 1972 in Paris, which would later become the first ICALP conference. He also quoted an excerpt from the preface of the proceedings for that conference, which I did copy verbatim, written by Maurice Nivat:
“If I were asked, in this preface, to explain how each of these forty five papers contributes to the solution of the main problems in Computer Science, I would be very embarrassed."
I leave it to you to interpret this quote :-)

The bulk of Leslie's presentation was supposed to deal with three topics that interest him right now, namely:
  1. Evolution
  2. Intelligence
  3. Human Brain.
The third topic, however, was not addressed during the talk for lack of time.

Regarding evolution, Leslie Valiant remarked that in the 19th century Darwin and Wallace posited an algorithmic mechanism for evolution: “random variation and natural selection.” Up to this day, there are no serious rivals to the Darwin/Wallace theory, but computer simulations of “random variation and selection” offer rather unimpressive results in evolving complex mechanisms.

Leslie mentioned the "quantitative mystery" behind evolution:
  1. How can such wonderful 3 billion length DNA strings be found in only 3 billion years?
  2. Does evolving complex circuits take exponential time?
In an effort to provide answers to these questions, Leslie compared evolution with learning, and mentioned that evolution can be treated as a form of computational learning from examples in which the course of learning is influenced only by the fitness of the hypotheses on the examples, and not by the specific examples. He explicitly mentioned work presented in a paper of his (see here) and in the recent paper

V. Feldman. Evolvability from learning algorithms, Proc. 40th ACM Symposium on Theory of Computing (2008).

Regarding intelligence, Leslie started by asking
What are people good at that computers are bad at?
His answer was "common-sense knowledge". He then provided the example of word completion (that he used in some recent experiments) and introduced the concept of robust logic, which he introduced about eight years ago. In his own words:
Robust Logic gives a common semantics for learning and reasoning, polynomial time algorithms for both, and soundness and completeness for reasoning.
Leslie described a recent experiment he carried out with Michael in which they developed a system to analyze about 500,000 sentences from the Wall Street Journal. They used a parser to find the structure of the sentences, learned rules to predict erased words and investigated whether chaining these rules leads to an improvement over baseline methods in predicting missing words. The results were a little better than those obtained using baseline methods.

Leslie concluded by saying that we need good "teaching material" for systems like the one Michael and he developed.

Friday, July 11, 2008

ICALP 2008

ICALP 2008 is now over, but the last six satellite workshops will take place over the coming week-end. MohammadReza Mousavi has already reported on some of the talks at the conference in a series of guest posts. Here I will just limit myself to a few remarks on the main events that took place since Wednesday. I will try to devote future posts to some of the other news from the conference.

On Wednesday, Bruno Courcelle (Labri, Universitè Bordeaux, France) delivered a plenary invited talk entitled Graph Structure and Monadic Second-order Logic: Language Theoretical Aspects. Courcelle is one of the 15 most cited French scientists and the most cited French computer scientist. (See In addition, he has become a member of the very prestigious Institut Universitaire de France (see Courcelle is one of the grand "old" men in theoretical computer science. In a career spanning about 35 years he has given fundamental contributions to the study of the logical, language-theoretic and algorithmic aspects of the theory of graphs. He is also one of the founders of, and main contributors to, algebraic semantics. In his talk, Bruno described the role that hierarchical decompositions and Monadic Second-order Logic play in the extension of methods and results from classic Formal Language Theory to the description of sets of finite graphs. Bruno is putting the final touches to a monograph on this topic that will be published by Cambridge University Press. (Present state of the work Part 1 : Chapters 1-6. Part 2 : Chapters 7-11.)

The scientific programme on Thursday was kicked off by an invited plenary talk by Peter Winkler (Dartmouth, USA). The talk, entitled Optimality and Greed in Dynamic Allocation, described a method for proving optimality in dynamic allocation problems that relies on the assumption that "it's right to be greedy." The method was developed while Peter was working on two problems which arose at Lucent Technologies.

The scientific programme for Thursday reached its climax with the award ceremony, during which the EATCS award and the Gödel prize where handed out. After receiving the EATCS award, Leslie G. Valiant (Harvard, USA) delivered an excellent 30-minute presentation focusing on three topics that interest him right now. The topics are:
  1. Evolution
  2. Intelligence
  3. Human Brain.
In his opinion, all these topics are computer science and are screaming for an understanding based on algorithmic approaches. Leslie described some of his work in this direction.

The Gödel prize talk, delivered by Daniel A. Spielman (Yale, USA), provided an outstanding finale for the day. In his talk, Dan explained the idea of smooth anallysis, how Teng and he thought of it and what he hopes the future will bring. Shang-Hua Teng (Boston University, USA) gave a personal and heartfelt introduction to the work they did to merit such a prestigious award.

The main event during the final day at ICALP was an invited plenary talk delivered by Javier Esparza (Technische Universität München, Germany). Javier's presentation was entitled Newtonian Program Analysis and presented recent work by his students and him that aims at using a computational approach to solving equations developed by Isaac Newton about 300 years ago in the analysis of computer programs. The talk presented exciting work and was beautifully and enthusiastically delivered. After the talk, Peter Winkler commented to us: "You saved the best for the last!" Javier closed the talk by saying that "Newton did it all 300 years ago, but he never saw Iceland!"

Wednesday, July 09, 2008

Dijkstra Prize 2008 to Baruch Awerbuch and David Peleg

During the meeting of the EATCS Council at ICALP 2008, I learned that the Dijkstra Award Committee has selected Baruch Awerbuch and David Peleg as the recipients of this year Edsger W. Dijkstra Prize in Distributed Computing. The price is given to them for their outstanding paper: "Sparse Partitions" published in FOCS 1990.

The prize is given for outstanding papers on the principles of distributed computing, whose significance and impact on the theory and/or practice of distributed computing has been evident for at least a decade. The Prize includes an award of $2000.

My Third Day @ ICALP 2008 (Guest Post by MohammadReza Mousavi)

This is the third guest post by MohammadReza Mousavi on ICALP 2008.

Ran Canetti: Composable Formal Security Analysis (Invited Speech)

Ran underscored the fact that the most challenging part of verifying security is to guarantee that protocols remain secure when put in arbitrary contexts and composed with other protocols. He defined a notion of security which basically requires that the observational behavior of a protocol in the presence of an "environment" machine (which can interfere in all possible ways) emulates the behavior of a perfectly secure protocol with a trusted third party. Combining symbolic methods with concrete cryptographic protocols is another aspect of composition theorem. Explicit analysis of all possible combination of such protocols is infeasible.

The message of the talk can be nicely summarized in the following nice quote (unfortunately forgot from whom):

"In security, the sum of the parts is a hole."
Addendum from Luca: Ran attributed the above quote to Dave Safford.

Patricia Bouyer: On Expressiveness and Complexity in Real-time Model Checking

Metric Temporal Logic (MTL) is a popular extension of Linear Temporal Logic (LTL) with quantitative timing, for which model-checking problem over dense-time models is undecidable. The main culprit for the undecidability is the presence of punctuality, i.e., formulae in which one can talk about exact time moments of events. Thus, punctuality-free fragments of MTL, such Metric Interval Temporal Logic (MITL), are proposed which are decidable. Patricia introduced a new subset of MTL, called coFlat-MTL, which can express properties such as global invariance, bounded response, and some kinds of punctuality (e.g., punctual response), for which model-checking over timed-automata models is in EXPSPACE. She also gave a tableau construction algorithm for this logic.

Antonin Kucera: Controller Synthesis and Verification of Markov Decision Processes

Antonin first showed why we need randomized and history dependent strategies (even bounded memory is insufficient) to control CMDP in order to satisfy qPCTL formulae. Then he presented a study of the complexity of the controller synthesis problem for Markov Decision Processes, which is the following question:

Is there a history dependent randomized strategy such that a given model satisfies a given qPCTL(*) formula?

(qPCTL is an extension of CTL, which allows for specifying properties like: with a probability less than .5, a state with a certain property will be reached.) According to his study, if I remember well, the controller synthesis problem for qPCTL(*) formulae is (2-)EXPTIME-complete in the size of the formula and polynomial in the size of the MDP.

Tuesday, July 08, 2008

Best Paper Awards at ICALP 2008

The best paper awards for ICALP 2008 were delivered this evening during the EATCS General Assembly.

The best paper award for track A went to the paper The complexity of Boolean formula minimization by David Buchfuhrer and Christopher Umans. The best student paper for track A was given to Jeff Phillips for his paper Algorithms for epsilon-approximations of Terrains.

The awards for track B were made to the papers
Finally the best paper award to track C went to the paper Making classical honest verifier zero knowledge protocols secure against quantum attacks by Sean Hallgren (Penn State University), Alexandra Kolla (UC Berkeley), Pranab Sen (Tata Institute) and Shengyu Zhang (Caltech). No paper qualified for the best student paper for track C.

There is a lot more to report from the conference, but time is short right now. Let me just point out that today ICALP 2008 featured a very special event, which was attended by about 300 participants, including the Icelandic Math Olympiad team, high school teachers of mathematics and members of the public at large. Peter Winkler (Dartmouth, USA) delivered a truly outstanding master class on mathematical puzzles entitled Puzzles You Think You Must Not Have Heard Correctly. It is the first time that ICALP features this type of event bringing a TCS conference of this calibre to a wider audience. Anna, Magnús and I are very happy to see how well it all went. Thanks to Peter for a truly inspirational talk!

When Peter presented the "Boxes in Boxes" puzzle, he said that

At many train stations, post offices and currier services around the world, the cost of sending a
rectangular box is determined by the sum of its dimensions; that is, length plus width plus height.
Magnús remarked that this is definitely true in Iceland for all train stations here. This is an example of logic at its best, and I'll use it next time I have to teach universal quantification over an empty set :-)

My Second Day @ ICALP 2008 (Guest Post by MohammadReza Mousavi)

This is the second guest post by MohammadReza Mousavi on ICALP 2008. Thanks to Mohammad for contributing this post! Further information on ICALP may be found at /dev/collective. See here for photos from the conference.

Track B of ICALP started today (7 July) afternoon. My body is not yet totally accustomed to the 24-hours-light scheme here in Reykjavik and thus, I decided take a leave from the morning sessions of Tracks A and C. What you read is a summary of a few talks given at Track B this afternoon. Some of the talks went beyond my limited understanding of their subject matters and thus, you may find inaccuracies in my report of the results, for which I apologize in advance.

Wim Martens: NFA Minimization

There exist well-known efficient state-minimization algorithms for DFA's. It is also known that bisimulation reduction for NFA's is efficient but it does not give you the minimal-state NFA. If I got it well, the bottom line, partially established by the ICALP'08 paper, is that all "interesting" state-minimization problems to non-DFA's (e.g., DFA's with multiple starting states or multiple, no matter how few, transitions with the same label) are NP-hard. By interesting Wim means, if I understood well, those minimizations that can lead to exponential reduction in size.

Hermann Gruber: RE Size

The minimal size of the regular expression for an automaton is known to be exponentially larger than the number of states, given that the alphabet is sufficiently large (due to Ehrenfeucht and Zeiger, JCSS, 1976; preprint available from here). In the present paper, the same result is extended to the case where the alphabet contains at least two elements.

Magnus Johansson: Extended Pi

Magnus presented an interesting extension of Pi in which names are replaced by arbitrary terms which can be equated using arbitrary equational theories (satisfying certain natural properties such as equivariance and equivalence) and also, aliasing for arbitrary terms is allowed (aliasing, or active substitution, basically introduces a new equation). The notion of bisimulation that comes with this this calculus (calculi, parameterized by the equational theory), is a very natural one: it requires the aliases of the two processes to be the same (up to the present equational theory) and the two processes to show the same behavior even under equational theories extended with new equations.

Monday, July 07, 2008

My First Day @ ICALP 2008 (Guest Post by MohammadReza Mousavi)

I am happy to provide a guest post by MohammadReza Mousavi, one of the workshop co-organizers for ICALP 2008, on his first day at ICALP 2008. Thanks to Mohammad for contributing this post!

Sunday July 6, 2008 was my first day at ICALP 2008. The conference was commenced the day before with the first day of the Dynamo workshop, but I had to be at a friend's Ph.D. defense session and an affiliated workshop. Thus, I lost the opportunity of being here right from the beginning. But there is Persian proverb which says: no matter when you catch a fish, it is fresh!

My first day was mostly spent at the SOS'08 workshop. It is nice to see fresh blood in the SOS community; there were a couple of graduate and Ph.D. students present at SOS'08 who have just started with SOS as their research subject. A warm welcome to all of them.

What follows is a biased overview of the talks presented in this very interesting workshop. Bartek and Matthew did an excellent job in organizing and chairing SOS'08; thank you very much Bartek and Matthew.

Vincent Danos: solid state concurrency

Vincent presented a general picture of biological systems and their huge dimensions which make any explicit state-exploration technique totally obsolete. He introduced the basics of the Kappa language which provides an abstract model for the (local) rules of interaction among biological agents. He presented a symbolic probabilistic abstraction for such systems (presented at VMCAI'08). There is a strong similarity between the situation here and that of random graphs as studied in statistical physics.

Observation: I found this talk extremely fascinating and very close and related to the ongoing work on the verification of distributed algorithms such as epidemic and gossiping protocols.

Michele Lorieti: Stochastic extension of process calculus, called CASPIS, for service oriented computing (SOC), which are by the way all the rage. The extension adds rates (for a negative exponential distribution) to synchronization constructs, and the rates are calculate in the same way as in PEPA.

Observation: Mixing synchronization with rates makes the semantics very difficult. Perhaps IMC and Markov Decision Processes are the way to go.

Muck van Weerdenburg: Automating soundness proofs

Muck translates SOS rules and the transfer condition for bisimulation into first order logic formulae and then by feeding a witnessing bisimulation relation for each axiom, the proof tool (initially Coq, then replaced by Muck's own proof tool). He has applied his tool . He even has a web-interface for his prototype.

Observation: Nice work. We need more of this kind of formalized proof environments for SOS.

Gustavo Ospina: Formalisation of C Language Interfaces

I must say I was a bit distracted during this talk. It reported on operational semantics of interfacing between C and another language called Russel, but the details have escaped my mind.

Michel Reniers, SOS with First Order Logic

Michel reported on a nice improvement over our joint SOS'07 paper on extending SOS with quantifiers. In his paper (joint with Muck van Weerdenburg), he presents a framework and congruence format for SOS which supports first order logic formulae (with infinitary conjunction) in the premise of the deduction rules.

Bartek and Luca raised the question whether we need such an expressive logic to specify the premises of the SOS rules and whether we can specify the same phenomenon with fragments of first order logic.

Eike Best: Relational Semantics

He presented the relational approach to operational semantics for non-deterministic sequential programs. Then, he presented the standard (denotational) semantics for such programs for both partial and total order semantics using Hoare and Smyth power domains. Then, he gave a generic way of presenting these semantics in a set-theoretic fashion by tailoring the definition of subset relation and relational compositions in each case.

Observation: Very neat talk to the foundations of semantics; reminding me of my first expositions to formal methods.

Dale Miller: Formalizing SOS in Logic

Dale started off by pointing out a dichotomy in the interpretation of computation, namely, computation as model (e.g., function, relation, or LTS) versus computation as deduction (e.g., in lambda calculus and logic programming). Being a logician, he stated his clear preference for the latter interpretation. Then, he gave an overview of syntax, from abstract to concrete, from strings to lambda-trees. Then he gave an introduction to the specification of operational semantics as a logical specification, showing that the traditional treatment of semantics as a logical formulae for nominal formalisms, such as pi calculus, is insufficient for proving impossibility of transitions and as a result bisimulation. He introduced then the nabla operator, as a substitute for universal quantification, which would enable us to prove impossibility of transitions (since it essentially enables us to prove that \lambda x . x cannot be unified with \lambda x .w).

Addendum by Luca: Dale had some great one-liners in his talk. The one I liked best was one he used in his reply to a question from Matthew Hennessy: "The world is too small for two self-dual quantifiers."

Peter Mosses: Implicit Propagation in SOS

SOS specifications often contain "redundant" information, i.e., they carry over lots of information that do not change along a transition or change in a very standand way (the change is propagated from the source of the conclusion to the source of the premise(s) and then from the target of the premises to the target of the conclusion). Peter presented an elegant way of "factoring out" such information and making SOS specs much more readable and also more reusable.

Together with Michel, we presented some initial ideas on writing a textbook about SOS. Peter Mosses suggested creating a wikipedia page for SOS, which is missing at the moment.

P.S.: Arnar updates his photos from ICALP'08 on a daily basis. Thanks to Arnar, Anna, Luca, Magnus and all the organizers for their excellent hard work.

Thursday, July 03, 2008

ICALP Coffee Directions

I guess that some of you will be looking for very good coffee places in Reykjavík close to the conference site. If so, you should definitely follow the ICALP coffee directions, courtesy of Pall Melsted. I can vouch for their accuracy, but read also my comment on his post.

By the way, Páll has his own blog, aptly called With High Probability. Link to it!

If I have time, I will try to post some information on eating out in Reykjavík. Any suggestions Páll?

Wednesday, July 02, 2008

Final ICALP 2008 Update

ICALP 2008 is now really upon us. The scientific feast will begin at 14:00 GMT on Friday, 4 July, with the start of the Second Training School on Algorithmic Aspects of Dynamic Networks (DYNAMO 2008) and will continue until Sunday, 13 July. The ICALP conference proper will be held in the period 7-11 July.

There are a little over 300 people signed up for ICALP and over 150 other colleagues will attend only some of the satellite events. This makes ICALP 2008 one of the best attended editions of the conference ever.

Full details about the conference and its 12 affiliated pre- and post-conference events are available at (See for the workshops.) The programme of talks for the main conference may be found at
The DYNAMO School will feature
The programme of DYNAMO is available at

The ICALP conference will have a very rich programme of contributed papers, which were selected from the programme committees from the 472 submissions they received. Here I limit myself to listing the invited talks that will be delivered at the conference and its affiliated workshops.

Sunday, 6 July, 2008:

08:40-09:30 M. Sotomayor, My encounters with David Gale (Match-up, Room 201)
09:00-09:45 Ashish Goel: Incentives based robust reputation and recommendation systems (Foundations of Information Management in Networks, Room 233)
09:00-10:00 Vincent Danos. A stochastic calculus of binding -- applications to the modelling of cellular signalling (SOS, Room 231a)
09:00-10:00 Andrej Bauer. Mathematically structured but not necessarily functional programming (MSFP, Room 235)
09:45-10:30 Maurizio Lenzerini: Integration and filtering of heterogeneous information (Foundations of Information Management in Networks, Room 233)
11:00-11:45 Muthu Muthukrishnan: Streaming and sampling algorithms for information aggregation in networks (Foundations of Information Management in Networks, Room 233)
11:00-11:50 K. Mehlhorn, Assigning papers to reviewers (Match-up, Room 201)
11:45-12:30 Giuseppe Persiano: Security of networks of low capability devices (Foundations of Information Management in Networks, Room 233)
14:00-14:45 Christian Scheideler: Algorithms for scalable and robust information systems (Foundations of Information Management in Networks, Room 233)
14:00-14:50 A. Roth, Kidney exchange: design and evolution of a computer-assisted matching mechanism (Match-up, Room 201)
14:00-15:00 Joseph Sifakis. Component-based construction of heterogenous real-time systems in BIP (Joint ICE and SOS, Room 231a)
14:00-15:00 Dan Piponi. Some elementary algebra and calculus of types and "antidiagonal" types. (MSFP, Room 235)
16:00-17:00 Dale Miller. Formalizing SOS specifications in logic (SOS, Room 231a)

Monday, 7 July, 2008:

09:00-10:00: Muthu Muthukrishnan, Internet Ad Auctions: Insights and Directions (ICALP, Room 131a-b)

Tuesday, 8 July, 2008:

09:00-10:00 Ran Canetti, Composable Formal Security Analysis: Juggling Soundness, Simplicity and Efficiency (ICALP, Room 131a-b)
16:30-18:00 Peter Winkler, Masterclass on Mathematical Puzzles (ICALP, Room 131a-b)

Wednesday, 9 July, 2008:

09:00-10:00 Bruno Courcelle, Graph Structure and Monadic Second-order Logic: Language Theoretical Aspects (ICALP, Room 131a-b)

Thursday, 10 July, 2008:

09:00-10:00 Peter Winkler, Optimality and Greed in Dynamic Allocation (ICALP, Room 131a-b)
16:30-18:00 Award ceremony, including talks by
  • Daniel A. Spielman (Yale, USA) and Shang-Hua Teng (Boston University, USA)) --- Recipients of the 2008 Gödel Prize
  • Leslie G. Valiant (Harvard, USA) --- Recipient of the 2008 EATCS Award

Friday, 11 July, 2008:

09:00-10:00 Javier Esparza, Newtonian Program Analysis (ICALP, Room 131a-b)

Saturday, 12 July, 2008:

09:15-10:15: Roger Wattenhofer. Algorithms for sensor networks, what is it good for? (Algosensors, Room 231a)
09:30-10:30 Terry Rudolph: Quantum computing, matrix permanents and why Bob Coecke isn't the only person who gets to do quantum mechanics by drawing trivial looking graphs (Quantum Physics and Logic/Development of Computational Models, Room 201)

Sunday, 13 July, 2008:

09:00-10:00: Helmut Schwichtenberg. Decorating proofs. (Classical Logic and Computation Invited, Room 233)
14:00-15:00: Stéphane Lengrand. Inhabiting negative types. (Classical Logic and Computation Invited, Room 233)
16:00-17:00 Andreas Winter: The Mother of All Protocols: Restructuring Quantum Information's Family Tree (Quantum Physics and Logic/Development of Computational Models, Room 201)

As you can see, there is going to be an embarrassment of riches and it won't be easy to choose what invited talks to attend during the workshop days.

My co-organizers and I hope that the participants will enjoy all aspects of the conference. In pure scientific fashion, I will keep my fingers crossed until the event is over :-)

If you are participating in ICALP and you'd like to provide guest posts reporting on the conference, send them to me and I'll be happy to post your contributions. It is highly unlikely that I will have time to post anything myself, apart from possibly reports on the EATCS General Assembly and on the Award Ceremony. In fact, as a local organizer, I wonder how many talks I'll be able to attend myself.

Despite the stress of being a local organizer, I am looking forward to this event.

Sunday, June 29, 2008

Kurt Gödel Centenary Research Prize Fellowship to Thierry Coquand

This is not really a very recent piece of news, but I became aware of it only a few days ago and, as far as I can tell, it is news that has not been covered in (TCS) blogs.

Thierry Coquand, of the Department of Computer Science and Engineering, University of Gothenburg, has been awarded a senior Kurt Gödel Centenary Research Prize Fellowship of 120,000 US dollars for his pioneering research into the foundations of mathematics. The prize is personal and is a global award made to a senior researcher, whose work builds on Gödel's achievements in mathematics and logic.

To my mind, it is not so surprising that the recipient of such a prestigious award in logic is a computer scientist. Logic is the calculus of computer science, and researchers like Thierry Coquand work at the boundary between mathematical logic and theoretical computer science. Thierry's research deals with big foundational questions such as:
  • What is the structure of mathematical proof?
  • Are there links between mathematical proof and computer programs?
Some of his answers to these foundational questions are at the core of the Coq theorem prover, a proof assistant that has been used to give, amongst other things, a fully machine-checked proof of the four-colour theorem.

Amongst his many achievements, Thierry Coquand also solved a long-standing open problem in measure theory, namely how to define in a purely inductive fashion the measure of Borel sets.

Congratulations to Thierry!

Wednesday, June 11, 2008

Colloquium in Honour of Ugo Montanari

Tomorrow, the Science Faculty of the University of Pisa (my Italian alma mater) will host the colloquium Concurrency, Graphs and Models in honour of Ugo Montanari on the occasion of his forthcoming 65th birthday. The invited speakers for the event are:
Apart from being outstanding scientists, the speakers cover some of the many areas of theoretical computer science to which Ugo has contributed over the years. Apart from being a very productive scientist, the DBLP lists 272 of his publications as of today, Ugo has given important contributions to the theory of constraint programming, to graph grammars, to the theory of concurrency, to the theory of abstract data types (final algebra semantics for ADTs), to categorical models of concurrent computation (see his paper Petri Nets are Monoids co-authored with Meseguer, and his work on the tile model) and to algorithmics (see for instance his efficient unification algorithm developed with Alberto Martelli), amongst others.

Apart from the influence that Ugo has had on the Italian TCS community via his research, one cannot help but marvel at the number of former students of his who are now in leading positions in Italian computer science. Ugo's influence, and that of his students, is one of the reasons why when I go to a concurrency theory conference, Italians seem to be everywhere.

On a personal note, some of the best academically-related memories I have of my student days in Pisa are related to a year-long course I took with Ugo during my third year. As I remember it, the course was a veritable tour-de-force covering topics in computability, automata and formal languages, abstract data types, some logic, denotational semantics and its application to programming-language semantics. The best part of it was, however, the week-long take-home group exam that we took. It was the only such exam I ever took in Pisa, and my friends and I learned a lot while working on it. By the time the assignment was over, we had composed a song about Ugo that showed the huge respect we had for him. One of the verses read: "this chain is too long, nobody can find an upper bound for it, but Montanari" :-)

Ugo was also the examiner for my MSc thesis at the University of Pisa, which I finished in 1986 under the supervision of Rocco De Nicola, who had been an MSc student of Ugo's himself. So, in some sense, I am an academic grandchild of Ugo's. Finally let me remark that Ugo was also one of the prime movers behind the BRA project CEDYSIS, under which I was employed during my doctoral studies at the University of Sussex.

Many happy returns, Ugo. Enjoy the day!

P.S.: Any reader who would like to author a guest post on Ugo's work or on his influence on the TCS research community is most welcome to send it to me. I'll be happy to post the contributions I receive.

Thursday, June 05, 2008

The Cost of Appointing Science Ministers Who Have No Clue About Science

I recently read this article on The Times On Line. For somebody like me who, for some possibly weird reason, still feels for the future of British science despite having left Britain in 1994 (and officially in 1996), this article makes for depressing reading. What is even more depressing is that appointing science ministers who have no clue about the importance of science for a modern society is a rather widespread phenomenon. In this specific case, I was also amazed to read that

A series of elementary arithmetical errors generated a budget shortfall of £80m....

One can fund a lot of good science with that money!

In the article, Neil Turok is quoted as saying that: “It is ludicrous that Britain’s participation in some of the greatest scientific projects of today such as the search for dark matter, the hunt for the elementary particles like the Higgs Boson and the first detection of gravity waves, is subject to the whims of people with no special competence and little experience of these matters..... What it reflects is the failure of the political establishment to understand just how important science is for Britain’s future. Advanced research drives the quality of higher education, science and technology and generates invaluable spin-offs.” I am afraid that this true for many other countries too, alas.

What can we do about it? We should definitely do the best we can to make more people interested in science and to make the general public understand how important science is for our modern society. We should certainly stress the points raised by Turok. However, we should not forget to tell everyone how important the journey of discovery that is part and parcel of any scientific endeavour is. Doing science is a humbling experience and teaches us to be self-critical. As Socrates famously put it, a wise man is one who knows what he does not know. I wonder how many science ministers possess this type of wisdom Wink

For the record, Neil Turok is relocating to the Perimeter Institute in Canada, which he will direct from 1 October 2008. The Perimeter Institute is supported by £75m provided by Lazaridis (of Blackberry fame) and his colleagues, and £50m invested by the Canadian government and the state of Ontario. (I could not fail to notice that the budget shortfall of £80m would have helped support a similar centre in the UK.) Turok is one of the prime movers behind the African Institute for Mathematical Sciences (AIMS). He gave one of the TED prize talks 2008. IMHO, the talk is well worth watching and I, for one, hope that Turok's wish will come true in the not-so-distant future.

Wednesday, May 28, 2008

CONCUR 2008: Accepted Papers

The list of accepted papers for CONCUR 2008 is now available here. There will be plenty of reading to do once the ICALP organization and the course I am delivering now are over.

On a separate, but ICALP-related, note, the winner of the 2008 Gödel Prize is the paper Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time by Daniel A. Spielman and Shang-Hua Teng, Journal of the ACM (JACM), 51(3), May 2004, 385-463. The results in the paper were first presented at the Annual ACM Symposium on the Theory of Computing (STOC 01), 2001, pp. 296-305.

The prize will be awarded at the conference during the award ceremony held on Thursday, 10 July. Both Daniel A. Spielman and Shang-Hua Teng will attend the ceremony.

Tuesday, May 27, 2008

Change of Editor for the BEATCS

The June issue of the BEATCS will be the last issue with Vladimiro Sassone as editor of the Bulletin. Maria Jose Serna will take over from Vladimiro, who will assist her for the next couple of issues.

Vladimiro has been in charge of the Bulletin for the last five years. He has streamlined the production process and made it web-friendly. (The whole Bulletin is now produced using pdflatex.) He has inaugurated two new columns, designed and implemented a new editorial style, and was a prime mover on the issue of open access for the BEATCS.

I like to think that the quality of the BEATCS has continued improving during Vladimiro's editorship, and the whole TCS community owes him a lot of gratitude for the enormous amount of energy he has put in the editorship of the BEATCS.

I wish Maria the best of luck for her new and important role. The BEATCS needs a strong editor, and it won't be easy to follow Vladimiro's footsteps and to improve on his work. Let's help Maria by contributing pieces to the BEATCS and by thinking about ways to make that publication even better. If you have any ideas, please post a comment. I will do my best to mention your suggestions during the EATCS council meeting at ICALP 2008.