Videos of talks by Friedman and Macintyre

There has been a fair amount of discussion recently on the FOM mailing list on whether the consistency of Peano Arithmetic is a legitimate mathematical problem in present day mathematical  culture. This discussion has been sparked by the talk Foundational Concerns and Mathematical Concerns that Angus Macintyre gave at the New Trends in Logic meeting. The video of Angus' talk is here. Perhaps some of the readers of this blog will want to have a look and reach their own conclusions. The person who asks most of the questions to Angus Macintyre is Harvey Friedman, whose own talk at the Vienna meeting can be seen here.

I have to say that Angus Macintyre kept his cool and maintained his thread admirably during his talk.

The videos of all the lectures may be found here, including the one delivered by Thierry Coquand when he received one of the prizes for 2008.

Jan Bergstra turns sixty

Jan Bergstra turns 60 today. Jan is one of the concurrency theorists whose work has had a lot of influence on mine, as well as on that of many others. However, his research interests are much broader and his research so far gives excellent examples of the power of algebraic tools and ideas in TCS.

According to Jan's Wikipedia entry, his main theoretical research programmes are:

• a systematic study of specification methods for abstract data types (starting in 1979, with John V. Tucker);
• the invention, development and application of process algebras, especially ACP (starting in 1984, with Jan Willem Klop, Jos Baeten and others);
• Module Algebra (starting in 1986, together with Paul Klint and Jan Heering);
• Program Algebra (starting in 1998, with Marijke Loots).

This gives a pretty fair reflection of the main thrusts in Jan's research work, and match pretty closely the topics covered by the five papers he has published in the JACM.

Apart from his scientific work, Jan Bergstra has had considerable influence on computer science in the Netherlands via his research and organizational activities. As an example of the impact he has had on CS in the NL, I limit myself to mentioning here that he has supervised over 40 PhD students, many of whom have become academic computer scientists (according to Wikipedia, at least 12 at professorial level).

As a recognition of his work, on May 18 this year, Jan has been inducted into the Royal Netherlands Academy of Arts and Sciences.

I wish Jan many happy returns for his 60th birthday and many more years of seminal scientific activity.

Addendum dated June 23: A special issue of Theoretical Computer Science devoted to the festschrift in honour of Jan Bergstra, edited by I. Bethke, A. Ponse and P.H. Rodenburg, is now available.

Rector Corradini, I Presume

This is not news anymore, but I am happy to report that Flavio Corradini was elected rector of the University of Camerino (Italy) on June 8. To the best of my knowledge, Flavio is now the youngest rector of an Italian university, and the first concurrency theorist to become rector of an Italian university. I wish him the best of luck for his new role, and hope that he will be able to continue doing some (theoretical) computer science.

Jos Baeten new general director of CWI

On June 1, I congratulated Jos Baeten for officially becoming the new chair of IFIP WG 1.8. Now, more congratulations to Jos are in order. Indeed, today the General Board of the Netherlands Organisation for Scientific Research (NWO) confirmed Jos' appointment as the new general director of the Centrum Wiskunde & Informatica (CWI) in Amsterdam. I learned the news from Jos himself, who is here in Reykjavik to attend Discotec 2011 and to deliver an invited talk at PACO.

The appointment of Jos as general director of CWI is excellent news for concurrency theory, and volume B TCS at CWI and in the Netherlands as a whole. In a way, it is also the "return of SEN 2", It is a bit ironic that Jos, who was one of the early directors of the very successful SEN 2 project, which was closed in 2008, returns now as general director of the whole institute. This may be seen as a case of "SEN 2 strikes back."

In any event, congratulations to Jos. I wish him a very successful term as director of CWI, which is one of the hotbeds of TCS research in the world. I look forward to seeing how CWI will develop under his expert leadership.

New Chair for IFIP WG 1.8

Jos Baeten has formally taken over the chairmanship of IFIP WG 1.8 on Concurrency Theory. I say "formally" because Jos has acted as de facto chair of the working group for some time already, since I decided not to run for a second term as chair.

Congratulations to Jos! I wish him the best of luck for his work as chairman of WG 1.8.

Accepted Papers for CONCUR 2011

I noticed that the list of accepted papers for CONCUR 2011 is available here. As usual, there are several interesting papers to look at. I just hope to have the time to do so. As someone said once: "Fermate il mondo! Voglio scendere!" ("Stop the world! I want to get off!")

Hubert Garavel received the Gay-Lussac Humboldt Research Award

These are good days for concurrency theory and computer-aided verification, at least judging by the awards bestowed on members of our community.

Yesterday I mentioned that the Presburger Award 2011will go to Patricia Bouyer. Holger Hermanns has now made me aware of the fact that Hubert Garavel recently received the Gay-Lussac Humboldt Research Award. (Thanks Holger!) Hubert is the fourth French scientist in the field of computer science to be awarded this prize. You can read more about the award to Hubert here. For the few readers who might not know his work, here I just limit myself to mentioning that Hubert is a pioneer in formal methods and verification tools for critical industrial systems. He is perhaps best known for being the prime mover behind the development of CADP, which is a popular toolbox for the design of communication protocols and distributed systems. CADP has been developed now for over twenty years, reflecting the very strong commitment to tool development based on elegant and useful theory that underlies Hubert's work.

Congratulations to Hubert and to Holger, who will be his host in Germany.

I note in passing that the awards to Hubert and Patricia offer further, albeit circumstantial, support on the strength of French TCS research.

Presburger Award 2011 to Patricia Bouyer-Decitre

The Presburger Award 2011 will go to Patricia Bouyer-Decitre.  See here for the details.

Patricia has contributed important results to the theory and applications of timed automata, a fundamental model of real-time systems.  In 2007 she received CNRS Bronze medal, awarded for outstanding achievements by a junior researcher.

I am very happy that this award went to Patricia. I had the pleasure of doing some work together with her at the very beginning of her career, and she has gone from strength to strength.

Congratulations to Patricia!

ERC Advanced Grant to Glynn Winskel

I just saw that Glynn Winskel has been awarded an Advanced Grant from the European Research Council for the period 1/05/2011-30/4/2016. The grant is for the project Events, Causality and Symmetry---the next generation semantics. (Extended Synopsis.)

This grant recognized one of the key players in the theory of concurrency over the last 20 years. Glynn's work on event structures, amongst other things, has had a lot of influence within my research community and it is good to see that this model plays a key role in the funded proposal. Glynn was also the director of BRICS, a research centre that had an enormous influence on TCS research in Europe and beyond.

Congratulations to Glynn!

Accepted papers for CALCO and TARK

The list of accepted paper for CALCO 2011 is here. The list of selected papers for TARK XIII is also available.

Quick reflections on ICALP 2011 (track B), part II: Conferences and long papers

During the review process for ICALP track B, a colleague wrote to me saying that he was planning to submit a paper longer than 70 pages to the conference, but eventually decided not to do so. While he was considering submitting the paper, this colleague was naturally wondering about the implications of submitting such a long paper to a conference with a 12-page limit on submissions. This academic told me that he thought that it would not be unreasonable to reject a very long paper submitted to ICALP  without even reading it. Such a decision could be backed up by a notification notice stating that "the paper is unverifiable given the available time and resources" or even "considering the paper is pointless since only 12 pages will be published."

I can understand very well why this colleague decided not to submit the paper to ICALP. Shrinking a 70+-page paper to 12 pages is a major effort, and one has to wonder whether a conference is the right outlet for such a lengthy piece of work. Indeed, one may argue that our conference publication structure does not lend itself to the publication of (very) long papers. However, I know of at least three exceptions (listed here in chronological order).

1. The ICALP 1990 paper in which Daniel Krob presented his equational axiomatizations of equality of regular expressions was 14 pages long, but the journal paper Complete Systems of B-Rational Identities (solving two problems posed by John Horton Conway in his monograph Regular Algebra and Finite Machines) that appeared in TCS in 1991 was 137 pages long. 
2. The ICALP paper in which Sénizergues introduced the decidability of DPDA equivalence is only 10 pages long, but the journal paper is 166 pages long.
3. The short paper by Martin Grohe at http://www2.informatik.hu-berlin.de/~grohe/pub/gro10.pdf was published in LICS 2010, but the full work takes a book that is still under development. See http://www2.informatik.hu-berlin.de/~grohe/pub/cap/index.html.
   

Now, one might ask what the purpose of those conference papers is. In some sense, my colleague was right in saying that they are "unverifiable" (given the length and time constraints imposed by conferences). I doubt that the conference reviewers went through all the details of the full versions of those papers, when they were available. Even a journal reviewer would probably not do so.

I guess that the answer is simply that the conference versions announce the results and "mark the territory" by saying "I did it". However, IMHO, the results only stand after the interested community has not found any serious errors in the full versions of the papers for a long time.

A separate issue is that of writing a conference paper based on a long full paper, which does justice to the main results and techniques presented by the authors in the full version in all the gory details. IMHO, conference papers reporting  on very long and technical developments are "trailers"  for the full version of the story, which is told elsewhere in all its glory. As a movie trailer, the conference paper serves the purpose of enticing potential readers to check out the full version by motivating the work, putting it in context, stating the achieved results, discussing their importance and giving a high-level sketch of the techniques and of the tools involved in the proof. (I am thinking here, for example, of the above-mentioned paper Grohe published at last year´s LICS, where he did precisely what I wrote above and, to my mind, did it well.) Of course, this is easier said than done..

Quick reflections on ICALP 2011 (track B): French TCS is alive and well

This is the first in what I hope will be a series of posts devoted to some reflections on ICALP 2011 track B. The executive summary is that, for what it is worth, I believe that French TCS is alive and well (at least as far as volume B TCS is concerned).

France was the country with the largest number of track B authors (42), the largest number of submitted papers (21.79) and the largest number of accepted papers (7). Easychair statistics aside, France is home to some research groups in TCS that have amazing strength in depth and breadth. To wit, consider the following three exhibits, with apologies to those that I am unable to mention explicitly here.

• Paris Diderot (aka Paris 7). This university is home to LIAFA and PPS, two large research laboratories hosting an enormous wealth of talent. (In passing, let me mention that PPS is a kind of little Italy, with six Italians holding permanent positions.)
• LSV at ENS Cachan.  The Laboratoire Spécification et Vérification (LSV) is the Computer Science laboratory of ENS de Cachan, and was founded in 1997. I had the pleasure of spending a month there in May 1998 as a visiting professor, but the LSV of today hosts a much larger team of researchers than it did then. The list of members is impressive. When Hubert Comon received a CNRS silver medal in 2008, he said that "I think that this is the best environment in the world to carry out research in computer science, thanks to a unique way of working and to a great scientific homogeneity." (See here, page 34, for the French original.) Of course, one can always debate this kind of statements, but it is hard to question the strength and focus of that group of academics. 
• LaBRI in Bordeaux. This is home to figures such as Bruno Courcelle, Anca Muscholl, Géraud Sénizergues, Igor Walukiewicz  and Pascal Weil, who are all members of the Formal Methods Group, which currently has 55 members.

It seems to me that these research centres are just the tip of a strong research iceberg in TCS. May they continue this way. 

EATCS Award 2011 to Boris (Boaz) Trakhtenbrot

The EATCS Award for 2011 will go to Boris (Boaz) Trakhtenbrot  for "his decisive influence on the developments of algorithms, and, more generally, of computer science as a whole in many ways." You can read a scientific "autobiography" written by Boaz for an LNCS volume devoted to his 85th birthday here (requires access to LNCS). I found the piece a fascinating read.

Congratulation to Boaz.

Here is what the EATCS web site says:

The EATCS Award is awarded annually to honor a scientist with widely recognized contributions to the field of theoretical computer science throughout a distinguished scientific career. The Committee, consisting of Pavlos Spirakis (Chair), Friedhelm Meyer auf der Heide  and Eugenio Moggi in charge of evaluating the nominations to the 2011 EATCS Award has come to the decision to honor Boris (Boaz) Trakhtenbrot with the EATCS Award 2011 for his decisive influence on the developments of algorithms, and, more generally, of computer science as a whole in many ways.The decision has been unanimously approved by the EATCS Council. The Award will be assigned during a ceremony that will take place in Zürich (Switzerland) during ICALP 2011 (July 4-8, 2011).

Best paper awards at ICALP 2011

The best paper awards for the three tracks at ICALP 2011 will go to the following papers:

Track A

• Malte Beecken, Johannes Mittmann and Nitin Saxena. Algebraic Independence and Blackbox Identity Testing.
• Shi Li. A 1.488-approximation algorithm for the uncapacitated facility location problem. (Best student paper)

Track B

• Olivier Carton, Thomas Colcombet and Gabriele Puppis. Regular Languages of Words Over Countable Linear Orderings.
•  Martin Delacourt. Rice's theorem for mu-limit sets of cellular automata. (Best student paper)

Track C

• Martin Hoefer.Local Matching Dynamics in Social Networks.
  
• Shiri Chechik. Fault-Tolerant Compact Routing Schemes for General Graphs. (Best student paper)

Congratulations to all the awardees!

Accepted papers for ICALP 2011 tracks A and C

The lists of accepted papers for ICALP 2011 tracks A and C are now available from the web site for the conference (both with and without abstracts). See here for track A and here for track C. I am no expert, but the lists of accepted papers look very impressive to me. It is also clear that blogging has a positive influence on acceptance of one's papers at ICALP track A :-) Congrats to Andrew, Bill, Lance and Scott, with apologies to other volume A bloggers I might have missed.

Source of a quote by Lazlo Babai

I once read the following quote attributed to Lazlo Babai: "What we need are not more theorems, but more proofs." I think that I originally read it on his Wikipedia entry, but the quote is not there anymore.

Can anyone tell me from where the quote originates, assuming my memory is not playing tricks with me? Thanks in advance!

Accepted papers for ICALP 2011 track B

The notifications and the reviews for ICALP 2011 were posted earlier today. I was the PC chair for track B and I freely admit that, during the electronic PC meeting,  I often felt that the job was too big for me. I owe all of my PC a great debt. I could not have mastered this PC chair job without the support of the members of the PC and without relying on their scientific judgement and professionalism. Indeed, I feel that I have learned a lot from my PC during the meeting.

The overall quality of the submissions to ICALP 2011 track B was unbelievably high. (My co-chairs tell me a similar story for the other two tracks, and this bodes well for the future of ICALP.) I feel that I have never been involved in the PC for a conference where the threshold for acceptance was so high. I wish that we could have selected at least ten more papers, but the number of slots was limited and we had to make some very hard choices. The authors of the many good papers that we could not select have my sympathy. I have no doubt that they will publish their submissions in a top-notch conference and/or journal soon.

There are several interesting topics for discussion that emerge from the field of submissions at this year's ICALP track B. I plan to devote a short series of posts to some of those that I have penned down during the PC meeting. However, this will have to wait until I have caught up with some of the many chores that have piled up on my desk over the last two months. For the moment, the list of accepted papers for track B is here. (See here for the list with abstracts.)

I look forward to a very exciting meeting in Zürich in July.

Student Scholarships at ICALP 2011

If you are a student and you are planning to attend ICALP 2011, read below. 

The EATCS (partly sponsored by MPI-INF) has provided ten 500-Euro student scholarships.  The ten scholarships will be used to support participation of students in ICALP 2011 by covering early registration and possibly some of the local expenses.

To apply for one of these scholarships, please send an email to . The application should be sent by April 19th, 2011, and should contain a motivation for the sponsorship request, one letter of recommendation, the curriculum vitae of the applicant, together with an indication of whether the applicant is an author or co-author of one of the papers selected for the conference.

The applications will be reviewed by the ICALP 2011 conference chairs and the PC chairs. Preference will be given to PhD students from countries where access to funds is limited who will present papers at the conference. Each applicant will receive a notification of acceptance/rejection of her/his application by email by April 30th, 2011.

SOS 2011: Call for Papers

The call for papers for SOS'11 (Structural Operational Semantics 2011) is out. SOS 2011 will be held as an affiliated event of CONCUR 2011 on September 5, 2011, in Aachen, Germany. The important dates are as follows:

• Submission of abstract: Friday 27 May 2011
  
• Submission: Friday 3 June 2011
  
• Notification: Friday 1 July 2011
  
• Final version: Friday 15 July 2011
  
• Workshop: Monday 5 September 2011

SOS is an event that is very close to my heart, so I strongly encourage my readers to submit good papers to the workshop. Let´s start sharpening our pencils now, but not in the sense of Halmos :-)

Accepted papers for LICS 2011

The list of accepted papers for LICS 2011 is out (with abstracts). The programme looks very strong, as usual.