ICALP 2012: First two days

ICALP 2012 is taking place at the University of Warwick. The programme is action packed, with many highlights and prizes. There are three tracks with 123 selected papers (71 for track A, 30 for track B and 22 for track C) out of 432 submissions (248 for track A, 105 for track B and 79 for track C). The acceptance rate was therefore around 28.5%. In addition, there are five invited talks and on day two David Harel delivered a Turing talk.

The conference is being attended by 210 participants (146 regular and 64 students).

There is so much going on that it is hard to give a detailed report on the scientific activities. I will thus limit myself to a few short remarks on some of the highlights of the first two days of the conference.

• The first two invited talks were delivered by Stefano Leonardi (Sapienza University of Rome) and Berthold Vöcking (RWTH Aachen). Both speakers focussed on algorithmic aspects of auctions. Stefano's talk was entitled On Multiple Keyword Sponsored Search Auctions with Budgets, while the talk by Berthold dealt with Randomised Mechanisms for Multi-Unit Auctions. 
• Leslie Ann Goldberg delivered a very inspiring talk on her joint paper with Mark Jerrum The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation), which received the best paper award for track A. Leslie brilliantly conveyed her enthusiasm for this amazing polynomial even to a layman like me, and gave us a glimpse of the rich mine of information that the Tutte polynomial contains about a graph. (W. T. Tutte also figured prominently during the very instructive excursion to Bletchley Park we enjoyed yesterday.)
• Manfred Kufleitner presented his joint work with Volker Diekert, Klaus Reinhardt and Tobias Walter that received the best paper award for Track B. Their truly remarkable result settles a long-standing open problem in formal language theory and may be found in the paper Regular Languages are Church-Rosser Congruential.  
• Tuesday saw an excellent Turing talk by David Harel on three strands of his research over the years that have been influenced by Turing's work.  I enjoyed it a lot and I finally got a chance of hearing David Harel deliver one of his trademark talks. 
• The Presburger award went to Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs). Venkat gave a talk that highlighted the web of connections that arise in his work and how tools from one area can find application in another one. He ended his talk was quoting the title of a talk by Avi Widgerson, namely "Depth through breadth". Mikkel Thorup gave a heartfelt presentation, describing Mihai Patrascu's work and personality. Several participants took photos for the Cheers to Mihai! web site. 
• The EATCS general assembly lasted until 8.50pm. Kurt Mehlhorn gave a very entertaining and thought-provoking report from the PC chairs. He said, amongst other things, that the submission data show that Track A researchers like to work in pairs or triples, Track B people like to work in pairs and that Track C papers are typically co-authored by a group of people. 
• ICALP 2014 will be held at the IT University in Copenhagen with Thore Husfeldt as general chairs. SWAT 2014 will take place just before ICALP and you will be able to enjoy the Copenhagen Jazz Festival too!

The conference is being organized by Artur Czumaj and his team. Kudos to them for having done a truly excellent job. Thanks to all of them!

I will try to post a telegraphic report on the rest of the conference as soon as I have a little time. I hope that other ICALP participants will share their opinions on the conference and their short reports as comments to my quarter-baked posts. 

LICS Test-of-Time Awards 2012

Prakash Panangaden has informed me that the LICS Test-of-Time Award for 2012 has gone to the following two papers:

• Thomas A. Henzinger, Xavier Nicollin, Joseph Sifakis and Sergio Yovine. Symbolic Model Checking for Real-Time Systems. 
• Jean-Pierre Talpin and  Pierre Jouvelot. The type and effect discipline.

The first article has received a huge number of citations for a LICS paper (1172 according to Google Scholar). It develops a thorough theory of symbolic model checking for timed CTL over finite automata with real-valued clocks.  It presents an algorithm that computes the set of states that satisfy a formula symbolically as a fixed point of a functional on state predicates, without constructing the state space. For this purpose, the authors introduce T_mu, a mu-calculus on computation trees over real-numbered time that has been studied by other researchers in further developments, and investigate its expressive power relative to that of timed CTL. Overall, this has been an influential contribution for the fragment of the CAV community dealing with real-time systems.

The second paper has been recognized an an important contribution to the theory of types and has received 331 citations  according to Google Scholar. The type and effect discipline is a framework for reconstructing the principal type and the minimal effect of expressions in implicitly-typed polymorphic functional languages that support imperative constructs.

Congratulations to the award recipients!

PhD Positions at IMT Lucca

IMT Lucca has issued its call for applications for admission to the IMT Ph.D. Program beginning in January 2013. Readers of this blog (or their students) might be interested in the track called Computer, Decision, and Systems Science, whose director is Rocco De Nicola.

The raw data about this call for PhD applications are as follows:

• 36 Ph.D. positions are covered by scholarships in the gross amount of 13,638.47€ /year.
• A limited number of additional positions without scholarships may also be offered.
• Ph.D. students will have tuition fees waived.
• Ph.D. students who are granted a scholarship have free accommodation in shared double rooms in the School residence halls (with the exception of students whose permanent residence is within 30km of IMT).
• Ph.D. students will have free access to the canteen services.
• Ph.D. students are covered by insurance against any accident and/or injury that may occur while they carrying out their Ph.D. activities.

For more information about IMT, I encourage you to look at their excellent recruitment video. IMT is growing and promises to become a hotbed of research at the intersection of computer science, control theory, economics and statistical physics. At least, the level of ambition is high.

Let me add, as icing on the cake, that Lucca is a lovely little town, which is close to many other beautiful Italian cities. Encourage good students to apply for the advertised positions!

Best paper awards at ICALP 2012

The preliminary version of the detailed programme for ICALP 2012 is now available here. While skimming through the programme, I learnt that the best paper awards for the conference will go to the following papers:

• Leslie Ann Goldberg and Mark Jerrum. The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation). Best paper for Track A. 
• Volker Diekert, Manfred Kufleitner, Klaus Reinhardt and Tobias Walter. Regular Languages are Church-Rosser Congruential. Best paper for Track B.
• Piotr Krysta and Berthold Vöckin. Online Mechanism Design (Randomized Rounding on the Fly). Best paper for Track C.

The best student papers are:

• Anastasios Zouzias. A Matrix Hyperbolic Cosine Algorithm and Application. Co-recipient of the best student paper for Track A.   
• Shelby Kimmel. Quantum Adversary (Upper) Bound. Co-recipient of the best student paper for Track A. 
• Yaron Velner. The Complexity of Mean-Payoff Automaton Expression. Best student paper for Track B.
• Leonid Barenboim. On the Locality of NP-Complete Problems. Best student paper for Track C.

Congratulations to all the award recipients!

The scientific programme for ICALP 2012 looks really action packed. The invited speakers are:

• Gilles Dowek (INRIA Paris)
• Kohei Honda (Queen Mary London)
• Stefano Leonardi (Sapienza University of Rome)
• Daniel A. Spielman (Yale)
• Berthold Vöcking (RWTH Aachen)
• Alan Turing talk: David Harel (The Weizmann Institute of Science)

During the conference, there will be presented three special awards: EATCS/ACM SIGACT Gödel Prize 2012, EATCS Award 2012, and EATCS Presburger Award 2012.

• EATCS and ACM's Special Interest Group on Algorithms and Computation Theory (SIGACT) awarded the Gödel Prize 2012 to three groups of researchers for their contributions to understanding how selfish behavior by users and service providers impacts the behavior of the Internet and other complex computational systems. The papers were presented by Elias Koutsoupias and Christos H. Papadimitriou, Tim Roughgarden and Éva Tardos, and Noam Nisan and Amir Ronen.
• The Presburger Award Committee 2012, consisting of Monika Henzinger, Antonin Kucera, and Stefano Leonardi (chair), has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs) as joint recipients of the 2012 EATCS Presburger Award for young scientists. (pdf)
• The EATCS Awards Committee consisting of Leslie Ann Goldberg, Friedhelm Meyer auf der Heide and Eugenio Moggi (chair), has unanimously decided to give the 2012 EATCS Award to Moshe Vardi (Rice University). (pdf)

The main conference will be preceded by a series of workshops taking place on Sunday, July 8.

Accepted papers at ICALP 2012

The list of papers that have been selected for the three tracks of ICALP 2012 is now available. The preliminary programme is also on line. This looks like an action-packed ICALP, with a plethora of interesting invited talks, award sessions and good-looking papers. I look forward to the conference.

EATCS and Presburger Awards for 2012

It is award time for the EATCS.

The EATCS Award for 2012 will go to Moshe Vardi. (The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.) You can read the laudatio here.

The Presburger Award Committee 2012 has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs, New York) as joint recipients of the 2012 EATCS Presburger Award for young scientists. See here for the details.

Congratulations to all the recipients of the two awards! 

Fifth Talk in the Alan Turing Year at Reykjavík University

The fifth talk in the Alan Turing Year at Reykjavík University was delivered this afternoon by my colleagues Yngvi Björnsson and Kristinn R. Thórisson. The talk was entitled Alan Turing's Contributions to Artificial Intelligence: Can Machines Think? and has been organized in collaboration with CADIA and IIIM. This was a thought-provoking and very enjoyable scientific event. In case you are interested the audio and the slides of the talk are here in .avi format. (Note: For technical reasons only the audio of Kristinn's presentation is available.)

In his presentation, Yngvi introduced the field of AI, its subbranches (applied AI, strong AI and cognitive AI) and highlighted Turing's main contributions to the field. On the other hand, Kristinn presented a critique of the Turing Test. Kristinn is a firm supporter of strong AI and his position on this matter can be summarized as follows. (I hope that I am not misrepresenting his views too much.)

1. The standard divide-and-conquer approach that we use in science to understand phenomena is not going to help us understand "intelligence", at least not if applied in the same way as has been done so far in AI, namely by using it in a reductionist way to remove features that are central to the phenomenon of intelligence.
2. The Turing Test was a very premature attempt at devising a test for the phenomenon of intelligence that forced upon much constructionist AI research the view that "intelligence is X, where X is some very simple manifestation of natural intelligence."

Overall, I left the talk with plenty to muse on, assuming I will have the time and the brains for this activity.

Reading material:

• “Computing machinery and intelligence” by Alan Turing (1950) (hosted by Hugh Loebner)
• The Turing test entry in the Stanford Encyclopedia of Philosophy.

PC-chair-authored papers at conferences

Perhaps it is just me, but I feel that there has been an increase in the number of papers (co-)authored by PC chairs selected for presentations at conferences. This seems to happen mostly at "specialist" conferences. I have noticed a similar trend for special issues of journals, to which guest editors are often allowed to submit contributions. In that case, the submission is handled by a member of the editorial board as an ordinary paper submitted to the journal.

Is it just me? If not, do you think that this is a good development?

Assistant professor position at Chalmers University of Technology

I have been asked to spread the news about this position. It looks like a very exciting opportunity for an ambitious young scientist.

We're looking for a talented and ambitions Assistant Professor in Information and Communication Technology at Chalmers University of Technology, Gothenburg, Sweden.

The position includes at least 80% research time and prestigious
status of Area of Advance at Chalmers:
http://www.chalmers.se/en/areas-of-advance/ict/Pages/default.aspx

The area of security is well in scope of the position. Please, help
spread the word!

Application deadline: May 1, 2012

Further info and application link:
http://web1.reachmee.com/i003/chalmers/se/vacdetail.aspx?commadseqno=502&postback%20=%20vacancies.aspx

J.E. Littlewood's take on "research strategy"

I really enjoyed reading the post Are You Working too Hard?, watched the linked videos and read some of the accompanying material from Uri Alon's web site. Whenever I stumble across this kind of material, I tend to go back to one of my favourite sources of inspiration related to the academic's art of work, namely the delightful piece The Mathematician's Art of Work by J.E. Littlewood. In that piece, "with a good deal of diffidence", Littlewood tries to give "some practical advice about research and the strategy it calls for."  Here is a summary of his advice.

• On days free for research, Littlewood recommends working at most five hours with breaks about every hour (for walks perhaps). Littlewood claims that without breaks one acquires the habit of slowing down unconsciously.
• Either work all out or rest completely. It is too easy to fritter a whole day away with the intention of working but never getting properly down to it.
• For a week without teaching duties, take one afternoon and the following day off. The day off should stay the same each week. 
• Take three weeks of holiday at the beginning of each vacation. This period is necessary and sufficient for recovering from the severest mental fatigue. 
• Morning work is far better than work done at other times of the day. From a certain point onwards, following severe concussion in 1918, Littlewood never worked after 6.30pm.
• Try to end your day's work in the middle of something; in a job of writing out, stop in the middle of a sentence. This will help warming up the morning after. 
• An ominous symptom of overwork is an obsession with the importance of work, and filling every moment to that end.

How would your work pattern compare to these pieces of advice? In my case, the answer would not be pretty and I feel that the same applies to many of my closest colleagues. The obsession with the importance of work has been there for a while and ........

Accepted papers for LICS 2012

The list of accepted papers for LICS 2012 is now out.

The first thing to note is that the PC for LICS 2012 has selected 61 submissions for presentation at the conference. By way of comparison, there were 37 papers that were presented at LICS 2011 (modulo counting mistakes I might have made.) This increase in the number of selected papers follows one of the changes that LICS 2012 promised to implement:

In response to concerns about LICS becoming overly selective with a too-narrow technical focus, the program committee will employ a merit-based selection with no a priori limit on the number of accepted papers.

Does this higher number of selected papers imply a "decrease in the quality of the conference programme", whatever that may mean? I have not read the papers yet, but a quick look at the list of selected papers and a brief look at the introduction of some of those available on line seem to indicate that this installment of LICS will be at least as strong as the others. Time will tell. My gut feeling is that this will be a very exciting conference.

I hope that someone attending the conference will be willing to send me a report for this blog. Let me know if you are interested in sending me a short report from LICS 2012.

Holding LICS in Croatia will be an interesting experiment. LICS 2012 will be hosted by the University of Dubrovnik, in Dubrovnik, which is a lovely town along the Adriatic sea. The location and the quality of the conference programme should entice many colleagues to attend the event. Unfortunately, the early registration fee looks pretty hefty to me: $450 for ACM, IEEE or ASL members and $600 for non-members are a lot of money at a time when travel money is scarce. (By way of comparison, the registration fee for ICALP 2011 in expensive Zurich was roughly €334.)

Last, but not least, it will be interesting to see which papers will receive the LICS Test-of-Time Award for 2012. Do you have any predications you'd like to share in the comment section?

Endre Szemerédi has been awarded the Abel Prize for 2012

Timothy Gowers just announced that  Endre Szemerédi has been awarded the Abel Prize for 2012. The citation reads:

"for his fundamental contributions to discrete mathematics and theoretical computer science, and in recognition of the profound and lasting impact of these contributions on additive number theory and ergodic theory."

This is a truly major day for discrete mathematics and TCS.  Look at  the Abel Prize web site and at the written version of the talk by Timothy Gowers,  addressed to a general audience, for more details.

ICE-TCS Annual Report for 2011

The ICE-TCS annual report for 2011 is now available. The main aims of our small centre are to establish TCS as a visible research area in Iceland, to attract students to it and to organize high quality TCS events in the country. We have been at it since 2005 and we hope to keep going.

Third Talk in the Alan Turing Year at Reykjavík University

The third talk in the Alan Turing Year at Reykjavík University was delivered last Thursday by Bjarni V. Halldórsson and dealt with Alan Turing's work on mathematicalbiology. (The event was organized jointly with the Icelandic Mathematical Society.) The audio of the talk is here in .avi format. The slides for the talk are here in .pdf format. Enjoy. 

This coming Thursday, Magnús M. Halldórsson will deliver a talk entitled The million dollar question: P vs. NP, and the legacy of Turing. I will post the audio of the talk as soon as it becomes available.

What does our job as academics consist of?

At this time of the year, my university produces its annual magazine. For good or for worse, typically I cannot resist the temptation to put pen to paper and to contribute one or two pieces to that publication. This year has been no exception, and I ended up writing a piece, aimed at students and the general public, that tries to explain what our jobs consist of. The reason for offering this specific contribution to the university magazine is that I have been feeling for a while that our students do not know what we do. And if they do not, what are the chances that anyone else will?

The result is Unveiling the Ivory Tower: The academic's art of work, just in case it may be of interest to any of my readers. 

Permanent Faculty Position in Computer Science, University of Camerino, Italy

Emanuela Merelli has asked me to distribute this announcement for a faculty position, which may be of interest to some readers of this blog.

Permanent Faculty Position in Computer Science
School of Science and Technology
University of Camerino

http://www.cs.unicam.it/home

The University of Camerino has opened a faculty permanent position at the level of Associate Professor in Computer Science for the School of Science and Technology.

We are interested in an lively and self-motivated candidate who is interested in working with existing faculty in one or more of the research areas within the Computer Science Division, in particular software engineering  and theoretical computer science. See
http://www.cs.unicam.it/home/component/content/section/2-research

for detailed information on the current research areas within the CS Unit.

Applicants should have published in international journals, had papers in proceedings of relevant conferences and given evidence of participation in international projects. The teaching language for some courses at Computer Science Division is English, hence applicants should have a track-record of teaching in English. Computer Science Associate Professor is expected to teach in the undergraduate, masters and PhD programs. Effective productivity and leadership in research, and interest in teaching are expected.

Applications must be sent, within 14 April 2012, to: Magnifico Rettore dell'Universita' di Camerino – Piazza Cavour 19/f, 62032 Camerino (MC).

See

http://www.unicam.it/servizi_online/cerca_bandi.asp

for detailed information.

Requirements for applicants: applications are welcome from candidates with the following qualifications:

a) candidates who received positive judgments according to “ Legge 210/1998” for the position corresponding to Associate Professor, candidates who were deemed fit for the position corresponding to Associate Professor according to “ Legge 210/1998” provided certification of fitness is still valid;

b) candidates who are already employed as associate professors in other universities i.e., since legislation “Legge 240/2010”;

c) scholars who are permanently employed in research or teaching activities at university level outside Italy in positions which are equivalent to those required in this call (according to ministerial equivalences).

Informal communication and discussions on any aspect related to the position are encouraged, and interested candidates are welcome to contact the chairman of the computer science division, Prof. Emanuela Merelli (emanuela.merelli@unicam.it), for further information.

The Computer Science Division of the School of Science and Technology at University of Camerino has about 500 students and 14 permanent staff members. The school offers undergraduate and graduate programs in computer science and the doctoral programme in Information Science and Complex Systems that currently hosts 18 PhD students. 

Situated up on the hill, Camerino, a beautiful little town of Central Italy with its medieval historical center hosts one of the most ancient university in Italy.

See

http://www.cs.unicam.it/home/component/content/category/15-living-in-camerino

for more information about living in Camerino.

Second Alan Turing Year Event at Reykjavik University

Last Friday, my colleague Ýmir Vigfússon delivered the second talk in the Alan Turing Year at Reykjavik University. His talk was entitled Alan Turing: The man who won the Battle of Britain and was organized jointly by ICE-TCS , the School of Computer Science at Reykjavik University and the Icelandic Mathematical Society.  In case anyone is interested, the audio of the talk, with the accompanying slides, is here in .avi format. I thoroughly enjoyed Ymir's talk and I strongly encourage my readers to listen to it. Thanks Ymir!

We plan to record all the talks in the series and to make them available on line here.

Faculty Position at IMT, Institute for Advanced Studies Lucca

Readers of this blog might be interested in this position, which has just been advertised. The call for applications states that:

Preference will be given to candidates performing research at the intersection between algorithms, theory and applications, and who are active in one or more of the following fields: analysis and modeling of massive data structures; graph theory and random structures; analysis and modeling of complex networks; machine learning; data mining; parallel and distributed computation.

Faculty Position
IMT Institute for Advanced Studies Lucca

IMT Institute for Advanced Studies Lucca  is an international Graduate School and Institute of Technology that strives to reach the fusion of theoretical comprehension and practical relevance. The following goals are at the core of IMT's mission statement:

* to establish itself as a research center that promotes cutting-edge research in key areas, structuring its Ph.D. Programs in close connection with research activity;
* to attract top students, researchers and scholars through competitive international selections;
* to contribute to technological innovation, economic growth and social development.

These objectives are met by means of the fundamental principles (the IMT Policy) adapted by the governing bodies of the Institute.

IMT has opened an international scouting procedure to recruit for a tenured faculty position in the following fields:

Computer Science and Engineering, Large Scale Data Mining, Graph Theory, Mathematical Statistics, Machine Learning

We will consider highly qualified candidates with a strong theoretical background in computer science, physics, statistics, information science, engineering, or mathematics, with an orientation towards research on processing huge amounts of complex data in the analysis of technical, socio economic or biological systems. Candidates must have an excellent record of high-impact international publications. They should have demonstrated remarkable ability in leading research groups, as well as experience in conducting/coordinating international projects.

Preference will be given to candidates performing research at the intersection between algorithms, theory and applications, and who are active in one or more of the following fields: analysis and modeling of massive data structures; graph theory and random structures; analysis and modeling of complex networks; machine learning; data mining; parallel and distributed computation.

Submit your confidential expression of interest at: http://www.imtlucca.it/faculty/positions/professors_positions/2011/application.php

Deadline is May 15th 2012.

Visit the Institute on YouTube (http://www.youtube.com/watch?v=q4gE-_2RrB8).

Nicolaas Govert de Bruijn (1918-2012)

I recently heard from MohammadReza Mousavi that Nicolaas Govert de Bruijn passed away on the 17th of February. In his long and productive life, de Bruijn gave contributions to several areas of mathematics and to theoretical computer science. Examples of his contributions are the De Bruijn sequence, De Bruijn's theorem, the De Bruijn–Erdős theorem in graph theory, the De Bruijn notation for terms in the λ calculus and his pioneering work on the project Automath, which was aimed at designing a language for expressing complete mathematical theories in such a way that a computer can verify the correctness of proofs in those theories. (Automath can be seen as the predecessor of type theoretical proof assistants such as the well known Nuprl and Coq.)

To celebrate de Bruijn's 90th birthday, TU/e organized a festive event.  Quoting from the web site for that event:

A number of colleagues, friends and admirers of Dick de Bruijn, from all over the world, wrote a personal letter as a birthday present for his 90th birthday, on July 9, 2008. The collection of these letters can be downloaded here.

Dick de Bruijn's lecture at the day of the symposium has been recorded on film. This film can be seen via this link.

Addendum: One of the letters in the above-mentioned collection is from Donald Knuth. In the letter, Knuth says that de Brujin coined the word "multiset" in a letter addressed to him from 1968. Knuth's letter also mentions the work of three of my former colleagues and ICE-TCS members: Anders Claesson, Mark Dukes and Sergey Kitaev.

ERC Advanced Investigator Grant to Dale Miller

Even though this is not really news any more, I am happy to report that  Dale Miller has been awarded one of the prestigious Advanced Investigators Grants by the ERC for the project ProofCert: Broad Spectrum Proof Certificates. This is a 2.2 million euro grant (about 3 million USD) for the five years 2012-2016. A news item pertaining to this award is here and the list of all awards for 2011 is available from this link.

The following excerpt is taken from the proposal’s abstract.

The ProofCert proposal aims at building a foundation that will allow a broad spectrum of formal methods—ranging from automatic model checkers to interactive theorem provers—to work together to establish formal properties of computer systems. This project starts with a wonderful gift to us from decades of work by logicians and proof theorist: their efforts on logic and proof has given us a universally accepted means of communicating proofs between people and computer systems. Logic can be used to state desirable security and correctness properties of software and hardware systems and proofs are uncontroversial evidence that statements are, in fact, true. The current state-of-the-art of formal methods used in academics and industry shows, however, that the notion of logic and proof is severely fractured: there is little or no communication between any two such systems. Thus any efforts on computer system correctness is needlessly repeated many time in the many different systems: sometimes this work is even redone when a given prover is upgraded. In ProofCert, we will build on the bedrock of decades of research into logic and proof theory the notion of proof certificates. Such certificates will allow for a complete reshaping of the way that formal methods are employed.

More technical details are available from the project's web page.

It is good to see that the ERC is actively supporting researchers of Dale's calibre in carrying out this kind of work. I look forward to seeing the outcome of this five-year project.

First Alan Turing Year event at Reykjavík University

Last Thursday, I kicked off  the Alan Turing Year at Reykjavik University  by delivering a talk for the general public entitled Alan Turing: The Father of Computer Science (organized jointly by ICE-TCS , the School of Computer Science at Reykjavik University and the Icelandic Mathematical Society).  In case anyone is interested, the audio of the talk, with the accompanying slides, is here in .avi format.

We plan to record all the talks in the series and to make them available on line here. 

It is not easy to give a talk for a general audience. In enjoyed the experience, but I was mightily relieved when the talk was over :-)

The Alan Turing Year at Reykjavik University is part of the Alan Turing Year, a centenary celebration of the life and work of Alan Turing.

What is a good research environment?

On January 27, I will be giving a ten-minute presentation at a town-hall meeting that will take place at Reykjavik University on the theme "What is a good research environment?". I roughly know what I am going to say, but I am curious to hear what would be the items on my readers' wish list when they think about a good research environment.

• What do you look for in a research environment you would be happy to work in? 
• What are the best aspects of your current research environment?
• What would you improve in your current research environment?

Two PhD fellowships at Reykjavík University in Design of Ad-Hoc Wireless Networks

I am very happy to post the following announcement of two Ph.D. fellowships on behalf of my colleague, and work-space neighbour, Magnús M. Halldórsson. I trust that it will be of interest to some of the readers of this blog and/or their students. The project "Design of Ad-Hoc Wireless Networks", which has Magnus as PI and sees the participation of ICE-TCS members Pradipta Mitra, Eyjólfur Ásgeirsson, Henning Úlfarsson and Ymir Vigfusson, has just been awarded a three-year excellence grant  by The Icelandic Research Fund.



Design of Ad-Hoc Wireless Networks

School of Computer Science, Reykjavik University

Two Ph.D. fellowships



Applications are invited for two Ph.D. fellowships at the School of Computer Science (SCS), Reykjavik University. The positions are part of a three-year research project funded by a grant-of-excellence by the Icelandic Research Fund, under the direction of Magnús M. Halldórsson.

Aim of the project

The aim of this project is to elucidate fundamental properties of wireless networks, broadly construed. Our focus is on general provable properties that hold for arbitrary configurations and are independent of situation-specific characteristics. We explore realistic models of interference, with the aim of bridging some of the gap between theoretical and applied research. We will also investigate practical protocols to disseminate information in general networks.



Some of the aspects of the projects include:

· Spectrum management, including game theory and spectrum auctions, and cognitive radio.

· Analysis of increasingly realistic models of wireless communication, including shadowing and obstacles, mobility, and network coding.

· Installation of a comprehensive wireless testbed, and the implementation of empirical confirmation studies.

· Resolution of fundamental open questions on wireless scheduling and capacity, and the design of communication primitives.

· Creating and evaluating protocols for information dissemination in combined wired and wireless networks.

· Devising practical systems and implementing applications for general networks.



The mode of operation of the project is three-pronged:

· Designing and implementing systems and kernel primitives.

· Conducting empirical studies in a wireless testbed, along with simulations studies.

· Designing and analysing algorithms with provable performance bounds.





Research environment

The research group consists of faculty members from three schools at Reykjavik University and collaborators at TU Aachen and ETH Zurich. The group includes Ýmir Vigfússon, Henning Úlfarsson and Pradipta Mitra (SCS), Eyjólfur Ásgeirsson (School of Science and Engineering) and Sverrir Ólafsson (School of Business and School of Science and Engineering). The project director is Magnús M. Halldórsson (SCS). Our primary collaborators are Berthold Vöcking (TU Aachen) and Roger Wattenhofer (ETH Zurich); we also collaborate with other world-class researchers in Europe, N-America, and Asia. The research group website is http://alnet.ru.is/sinr.html.


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

Qualification requirements

Applicants for the Ph.D. fellowships should have a MSc degree in Computer Science, or closely related fields, and have a solid background in the analysis of algorithms and a good understanding of networking. One of the studentships is expected to be systems-oriented, for which an experience with systems design and implementation is essential. The other will be focused on algorithmic analysis, for which mathematical competence is crucial.

Remuneration

Each Ph.D position provides a stipend of 250,000 ISK (roughly 1600€[1]) per month before taxes, for three years, starting as early as possible and no later than September 2012.

Application details

By Friday, 15 February 2012, interested applicants should send their CV, including a list of publications where applicable, as a PDF document to mmh@ru.is, together with a transcript of their academic record, a 1-2 page statement outlining their suitability for the project and the names of two referees who can comment on the research potential of the candidate.

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

About the School of Computer Science at Reykjavik University

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

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

Information about Ph.D. studies at the School of Computer Science is available at
http://en.ru.is/departments/school-of-computer-science/ph.d-studies/



[1] Up-to-date Exchange Rate can be obtained from http://sedlabanki.is/?PageID=183

Merry Christmas, if it comes.....

From xkcd. My daughter would not be very happy with this Zeno behaviour :-)

Accepted papers for FOSSACS 2012

The list of accepted papers for FOSSACS 2012 is now available. The competition for the available slots was very hard, and several deserving submissions could not be selected for the conference.

On a personal note, the more I serve on PCs for competitive conferences, the more I have the feeling that the quality of the competition is increasing. The same holds true for grant applications, job applications, promotions and just about any other aspect of academic life.

News from the LICS Community

Here is some news I just discovered by looking at the web page for LICS 2012.

Highlights and changes for LICS 2012

1. Starting 2012, LICS is jointly organized by ACM and IEEE, and is cosponsored by ACM SIGACT and the IEEE Computer Society's Technical Committee on Mathematical Foundations of Computing.
2. In response to concerns about LICS becoming overly selective with a too-narrow technical focus, the program committee will employ a merit-based selection with no a priori limit on the number of accepted papers.
3. LICS 2012 will continue the tradition of pre-conference tutorials that was initiated in 2011. This year, Jan Willem Klop will give a tutorial on term rewriting systems and Andre Platzer will give a tutorial on logics of dynamical systems.
4. Special Events and Invited Lectures: There will be an invited lecture by Robert J. Aumann, winner of the 2005 Nobel Prize in Economic Sciences, and a plenary session in honor of Alan Turing on the occasion of his centenary, with talks by Robert L. Constable, E. Allen Emerson (co-winner of 2008 A. M. Turing Award), Joan Feigenbaum, and Leonid Levin. 

These are very interesting developments for the LICS community, some of which should be of interest for the TCS community as a whole.

Development A above paves the way to the formation of an ACM Special Interest Group on Logic in CS, say a SIGLOG, about which I have heard reports in private conversations with key players in the LICS community. Such a special interest group would play an important role in the development of volume B TCS research in North America.

Development B is most interesting and might be a watershed event, if it pans out. LICS plays the role of FOCS/STOC for the volume B TCS community and I believe that all of TCS will be interested in observing the outcome of the LICS 2012 experiment. Typically, the quality of an average LICS submission is very high and this new policy might encourage even more submissions to the conference than usual. How will the PC handle these submissions? Will the conference move to parallel sessions? Will this development decrease the value of the "LICS currency"? Will other conferences follow the lead of LICS, if the experiment "succeeds"?

Time will tell. In any event, this is a courageous step taken by the LICS conference and I look forward to seeing how it will affect the conference and the LICS/TCS community.

Last, but not least, items C and D above look exciting. I have heard from several sources that the tutorials at LICS 2011 were a resounding success. (See here, here and here for the slides used by Prakash Panangaden, one of my favourite speakers, in his tutorial on Semantics. Albert Atserias gave a tutorial on Finite Model Theory.)

Standards for promotions

My department is developing its strategy for the next five years. As part of this strategy work, we are working on a "promotion strategy" and we are discussing standards for promotion to associate and full professor positions. Needless to say, there is a wide array of opinions amongst my colleagues on this point. In order to obtain a broad survey of current best practices, let me ask any reader out there:

• What does it typically take to be promoted to associate and full professorships at your institution? 
• What role does teaching performance play in such decisions? And how is it measured?
• What are the incentives to undergo a promotion process, apart from the obvious ones like tenure and possibly higher wages?

Thanks in advance!

Dr. Cimini, I presume

Last Friday, Matteo Cimini successfully defended his PhD thesis entitled Contributions to the Meta-theory of Structural Operational Semantics. Congratulations to Dr. Cimini! I expect that his thesis will be available on line soon, but, for the moment, you can read some of the papers that form the bulk of that tome.

A PhD is not enough, however. I wish Matteo the best of luck for his future career. 

EATCS ballot on the future of the publication of the ICALP proceedings

Today, the European Association for Theoretical Computer Science started a ballot on the future of the publication of the proceedings of ICALP. This is a very important decision for the EATCS, and for the ICALP community in general. As chairman of the publication committee of the EATCS, I urge all the members of the TCS community who have a right to vote as members of the EATCS, to give this matter serious thought and exercise their right to express an opinion on whether future ICALP proceedings should be published with Springer or with LIPIcs. Note that if you attended ICALP 2011, ESA 2011 or MFCS 2011, you have the right to vote since your registration fee probably included a one-year membership of the EATCS.

Note also that the result of the  ballot will only take effect if at least 25 % of the EATCS members participate. Otherwise, the proposal of the EATCS council to recommend to the EATCS membership to go along with Springer for the next four years will take effect automatically.

The ballot on the future of the publication of the ICALP proceedings, as well as all the supporting documentation,  can be found here.  I do hope that you will take time to consider this matter and vote as soon as possible.

Assistant Professor position in Modelling and Analysis of Concurrent Systems at IMT Lucca (deadline October 31st)

Perhaps this announcement will be of interest to some of the readers of this blog. IMT Lucca is an exciting place and there will definitely be some competition for the position. 


Addendum dated 7 October: This video issued by IMT Lucca gives an enticing introduction to that academic institution. Do have a look, if you are interested in applying for this position.

The IMT Institute for Advanced Studies Lucca invites applications for an Assistant Professor position in the areas of foundations and formal specification of concurrent (distributed, mobile, autonomic) systems; quantitative and qualitative modelling and analysis of concurrent systems and design and development of software tools to support their formal analysis; applications to socio economic systems.

IMT Lucca (http://www.imtlucca.it) is a public international Graduate School and Institute of Technology that acts as a research university with the aim of forming human capital in disciplines characterized by their high potential for concrete applications. IMT strives to reach the fusion of theoretical comprehension and practical relevance. 

The Assistant Professor will be a part of the Research Unit "System Modelling and Analysis" (SysMA, http://sysma.lab.imtlucca.it/) in the Computer Science and Applications area of the Institute, and will perform research activities, tutorship and mentoring of Ph.D. students, limited teaching of graduate courses and participation in the development of the research activities of the Institute. 

Appointment compensation packages will depend on the candidates and their records of accomplishment, but are competitive on an international level. Applicants must be able to teach graduate courses in English; knowledge of Italian is not required.

The deadline for application is October 31st, 2011 12:00 pm CET.

Interested candidates must apply before the deadline by filling in the online application form at http://www.imtlucca.it/faculty/positions under "Junior Faculty Recruitment Program". They will also be asked to submit a CV, a research paper (published or working) and the name and contact details of three referees.

For further information about the position, applicants can refer to 

http://www.imtlucca.it/faculty/positions/junior_faculty_recruitment_program.php#modelling_concurrent_systems

or can contact either Rocco De Nicola or Sara Olson: researchers.opening@imtlucca.it.

LICS 2012 Test-of-Time Award

The latest issue of the LICS Newsletter (dated July 29) mentioned the appended information related to the LICS 2012 Test-of-Time Award. 

I strongly encourage the members of the LICS community to send their comments to Andre Scedrov (scedrov@math.upenn.edu), who chairs the award committee. As usual, the committee is faced with a very hard choice and they can do with some input from the community.


LOGIC IN COMPUTER SCIENCE (LICS) - TEST OF TIME AWARD

• The LICS Test-of-Time Award recognizes a small number of papers from the LICS proceedings from 20 years prior that have best met the "test of time".
• The LICS 2012 ToT Award committee consists of
• Martin Grohe,
• Prakash Panangaden,  
• Andre Scedrov (Chair), and  
• Ashish Tiwari.
• The committee will select between 0 to 3 papers  that appeared in LICS 1992 proceedings. All papers are nominated by default, but the  committee welcomes input from our community: please send your comments to  Andre Scedrov (scedrov@math.upenn.edu) which will be shared only among the committee members.  
• LICS 2012 ToT award will be presented during the business meeting at LICS 2012  to be held in Dubrovnik from June 22 to 25, 2012. 
• The list of papers from LICS 1992 is available at  http://www2.informatik.hu-berlin.de/lics/archive/1992/index.html 
• The information about LICS ToT award and the list of past winners is available at  http://www2.informatik.hu-berlin.de/lics/archive/test-of-time-award.html

October 2011 issue of the BEATCS Concurrency Column

I have just submitted the material for the October 2011 issue of the BEATCS Concurrency Column. This instalment of the column consists of a double bill:

• Interval Temporal Logics: a Journey by Dario Della Monica, Valentin Goranko, Angelo Montanari and Guido Sciavicco. [PDF]
• Assertional and Behavioral approaches to concurrency by Uri Abraham. [PDF]

The first piece is a survey  devoted to interval temporal logics. The article presents the main developments in the study of interval temporal logics over the past 10 years (a field of research to which the authors have contributed substantially) and outlines some landmark results on expressiveness and (un)decidability of the satisfiability problem for the family of interval logics. The authors give us a guided tour of this body of work, which, to my mind, deserves to be better known within the concurrency-theory community.

The second contribution is a a piece by Uri Abraham in which he compares two proofs of the mutual-exclusion property for the well known algorithm by Peterson: an assertional proof and a behavioural one. The article outlines a framework within which the behavioural approach can be formalized in a way that retains the intuitive content of the behavioural reasoning.

This is my last issue as editor of the Concurrency Column. I have been editing the column for the last eight years, and I feel that it is time to step down. The column will benefit greatly from a fresh perspective on the world of concurrency theory and I look forward to reading the pieces that will appear in future issues.I thank the contributors to the Concurrency Column over the last eight years and all my readers.

12 PhD positions in Computer Science and Engineering at IMT Lucca

Courtesy of Rocco De Nicola, here is an exciting opportunity for excellent students, which I am happy to advertise.

The institute for advanced studies IMT Lucca (Italy) announces 12 PhD positions in Computer Science and Engineering. The deadline for applications is September 28, 2011.

IMT (http://www.imtlucca.it/) is a research institute located in Lucca (Italy); courses are taught exclusively in English.

The PhD Program (https://www.imtlucca.it/phd_programs/computer_science_engineering/) coordinated by Rocco De Nicola aims at preparing researchers and professionals with broad training in the foundations of informatics as well as in applications to a variety of cutting-edge systems and disciplines.

A number of PhD students will be selected for working within the the two newly founded Research Unit:

SysMA (http://sysma.lab.imtlucca.it/

)
lead by Rocco De Nicola doing research on concurrent (distributed, mobile, autonomic) systems modelling and analysis
and
Dysco (http://dysco.lab.imtlucca.it/)
lead by Alberto Bemporad doing research on control and optimization technologies.

In addition, students will be selected to work on topics related to medical imaging, and imaging for the life sciences
http://users.eecs.northwestern.edu/~stsaft/#Openings

We hope that you may consider applying for and/or signaling these opportunities to colleagues and collaborators.

======= DETAILS ON THE ADVERTISED POSITIONS =======
6 IMT scholarship (12.423 EUR after taxes) plus accommodation and free meals (lunch and dinner).
1 MIUR scholarship (12.423 EUR after taxes) plus free meals (lunch and dinner).
5 positions to be funded with internal projects or third-party scholarships (negotiable salary) that come with a research budget of 3.000 EUR offered by IMT and free meals (lunch and dinner).

For further information please visit
http://www.imtlucca.it/phd_programs/call_for_applications/index.php
and/or contact the sender of this mail.

PhD positions at the University of Camerino, Italy

Emanuela Merelli has asked me to circulate the following announcement of eight PhD positions at the University of Camerino, Italy. The deadline for applications is very close, but perhaps some readers (or some of their students) might want to apply. 

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

We kindly remind you that  the PhD call for applications at University of Camerino is still open. See

http://www.unicam.it/laureati/dottorato/call.asp

There are 8 fellowships available for the Doctoral Study Programme in Information Science and Complex Systems. See

www.cs.unicam.it/merelli/PhD-Informatica.pdf

The deadline is approaching, 26 August 2011.

2011 CNRS Silver Medal to Jean Goubault-Larrecq

Jean Goubault-Larrecq receives the 2011 CNRS Silver Medal. The web site with the list of medal winners states that:

La Médaille d'argent du CNRS distingue un chercheur pour l'originalité, la qualité et l'importance de ses travaux, reconnus sur le plan national et international.

So, Jean is recognized for the originality, the quality and the importance of his research work. Congratulations to Jean for the award, and to LSV as a whole for yet another achievement.

The silver medal for mathematics went to François Loeser.

Accepted papers at ESA 2011 and MFCS 2011; CFP for FSTTCS

The list of accepted papers for ESA 2011 is here. (My colleague Magnús Halldórsson was the PC chair for ESA 2011.) Ditto for MFCS 2011.

The submission deadline for FSTTCS is just two weeks away. The call for papers is here. The list of invited speakers for the event is stellar:

• Susanne Albers (Humboldt-Universität zu Berlin, Germany)
  
• Phokion G. Kolaitis (Univ. of California, Santa Cruz, USA)
  
• John C. Mitchell (Stanford University, USA)
  
• Madhu Sudan (currently at Microsoft Research New England, and on leave from MIT, USA )
  
• Moshe Vardi (Rice University, USA)
  
• Umesh V. Vazirani (Univ. of California, Berkeley, USA) 

Do submit! 

LICS 2011 Test-of-Time Award

The LICS 2011 Test-of-Time award was given yesterday to 

• Patrice Godefroid and Pierre Wolper for their paper A Partial Approach to Model Checking, 
• Dale Miller and Joshua Hodas for their paper Logic Programming in a Fragment of Intuitionistic Linear Logic and 
• Dexter Kozen for his paper A Completeness Theorem for Kleene Algebras and the Algebra of Regular Events.
  

This year's award was given to papers presented at LICS 1991 that have stood the test of time and have had considerable impact since their publication. (Source: Prakash Panangaden)

Congratulations to all the award recipients!

FPSAC 2011

I have received the following short report on FPSAC 2011 from Henning Úlfarsson, which I post with pleasure. Sources within my extended family told me that the conference was very well attended. The lecture hall was packed and it was nearly impossible to get close to the posters. The lure of Iceland as a conference location strikes again :-)

The 23rd International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2011, was held in Reykjavik, Iceland on June 13-17, on the premises of the University of Iceland. This year's conference was dedicated to the memory of Philippe Flajolet, who passed away recently, and was very influential in the field of algebraic and analytic combinatorics. (An obituary for Philippe Flajolet may be found here.)

The conference featured 10 invited speakers, 27 talks, 53 poster presentations as well as an afternoon of software demonstrations. The topics ranged from various aspects of combinatorics to applications such as shallow water waves and genome arrangements.

More information can be found on the website http://combinatorics.is/.

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.