Friday, December 28, 2012

A Short Play on Alan Turing

The inspiration from this piece, which I post as a finale for the Turing Year events at Reykjavik University, comes from "Il Bivio di Alan" by Mario Cristiani, Chiara Bodei and Maria Rita Lagana, which was in turn inspired by the radio drama "Turing's Test" by Phil Collinge and Andy Lord. I thank Chiara Bodei for sharing their piece with me. The text below is not much more than a translation of "Il Bivio di Alan", which you can watch here (in the original Italian version). The version of the play below was acted at Reykjavik University on Thursday, 29 March 2012.

Alan M. Turing: The Man and the Scientist

This dialogue is set in a simply furnished bedroom. A man, Alan Turing, is lying on the bed motionless. On the side table lies a half-eaten red apple. A desktop computer suddenly materializes out of thin air  on a desk next to the bedroom's window. The computer screen lights up, the machine boots up and produces a jingle similar to the Window's one .

Computer: Start-up completed. Time reset. Welcome everyone. Today is the 7th of June 1954. The man who lies on the bed next to me is Alan Mathison Turing. He just committed suicide by eating an apple poisoned with cyanide, just like Snow White in his favourite fairy tale.

Many of you probably won't know who Alan Turing was, but you all use computers like me without knowing that we are children of his genius. His code-breaking work at Bletchley Park during World War II was instrumental in deciphering the Enigma code used by the Nazi Navy, and definitely shortened the war. Alan Turing is also considered by many to be the father of Artificial Intelligence. He realized very early on that computing machines could be used to solve symbolic manipulation problems, such as playing checkers and chess, and solving jigsaw puzzles. This realization led him to ask a fundamental philosophical and scientific question: "When can a computing machine be said to be intelligent?" To answer this question, Turing proposed the Turing Test, which was based on the idea that a computer could be said to exhibit intelligence if a human interrogator could not distinguish it from a human being. HAL 9000, the computer in 2001 Space Odyssey supposedly passed the Turing test. To this day, I am not aware of any of my fellow machines that can do so. However, in 2012, often humans are tested using CAPTCHAs, which are reverse forms of the Turing Test in which humans try to convince a computer that they are indeed humans!

One would expect that,  during his life, Turing would have been celebrated for all these monumental achievements. However, nothing could be further from the truth. Turing's life was a sad one. He was a homosexual at a time when homosexuality was a crime in the UK, he was convicted of gross indecency and was given a choice between imprisonment or chemical castration via oestrogen hormone injections. He chose the latter and, on this day, he committed suicide.

Computer: Alan, Alan, wake up! Can you hear me?

Turing: Who....what are you?

Computer: I am the product of your imagination. I am your machine.

Turing (as if talking to himself): I did not know that poison had this effect.

Computer: This has nothing to do with poison. I am the incarnation of your Universal Turing Machine, of the programmable computer you dreamt up in 1936 while solving a problem in mathematical logic. Since then, it was only a matter of time before someone built me based on your detailed plans. You could have done so yourself, had you not stopped dreaming.

Turing: I did not want to stop, but they turned my life into a nightmare. They came to ask for my help when my nation needed me to understand encrypted messages exchanged by the Nazi forces, but then I became a liability because of my homosexuality.

In all honesty, I loved to work at Bletchey Park and to develop algorithms for code breaking, to discover meaning where there seemed to be none, to develop machines that could help us analyze increasingly more sophisticated encrypted messages. It was like a game, it was like testing oneself by running a marathon in 2 hours and 46 minutes. I am still proud of that time.

Then, the same people who enlisted my help forced me to act against my own self. But why am I saying this to you? You do not think!

Computer: Are you sure? After all, you are the one who argued that machine intelligence might be possible and invented the Turing Test! Didn't you suggest that a machine be built to emulate the thinking process of a child and that it be trained to develop into a machine that could think like an adult human being?

Turing: Yes, I did. The times were not ripe though. Just as they were not ripe for my active homosexuality. The authorities were afraid that I could leak secrets to handsome Russian spies, I guess. (Laughs bitterly.)

Turing the scientist was of help to them: they treated that one well during the war and honoured him with an OBE. However, Turing the man was indecent, immoral and even dangerous for national security.

Computer: But, the man and the scientist are one! They should have seen what your worth to humanity had been.

Turing: My worth.... Do you know how much I am worth? A shirt, five fish knives, a pair of trousers, three pairs of shoes, a compass, an electric shaver and an open bottle of sherry. This is what I am worth!

Computer: What is that?

Turing: This is what my boyfriend took from my apartment. This is the list of things I denounced to the police as stolen goods. I was in love with him. I do not think that you can understand.

Computer: Perhaps not. What happened afterwards?

Turing: I admitted my homosexuality and told them that there was nothing wrong with it, that one day homosexuality will not be a crime any more.

They offered me a choice: imprisonment or a "cure" via injections with female hormones.

Computer: I know that you chose the latter.

Turing: Yes, and look at what I have become. I have started growing breasts, I have the voice of a female actress and my mind has gone with my body. Do you know how it feels not to be able to recognize yourself any more? This is what remains of Alan Turing: a broken mind in a broken body --- the body of a loser.

Computer: You are wrong. This is not what will remain of you. So many ideas and technological advances converged to create a modern computer like me that it is foolhardy to give one person the credit for inventing it. But the fact remains that everyone who, in the year 2012, taps at a keyboard, sending an email, or opening a spreadsheet or a word-processing program, is working on an incarnation of your Universal Turing Machine.

You will be remembered for your scientific legacy, which will have a far greater impact than, perhaps, even a visionary like you could have ever imagined.

Turing: This will not help me now that I am dead.

Computer: May I ask you why someone like you, who could run a marathon and endure the ensuing pain, ended up committing suicide?

Turing (after a long pause): Perhaps so that the memory of Turing the man could live forever like the one of Turing the scientist. Perhaps, for once and unexpectedly, logic failed me.

The lights slowly fade and the room darkens.

Wednesday, December 19, 2012

Upcoming Deadlines for the EATCS Awards

The deadline for submitting nominations for the EATCS Award 2013 and the Presburger Award 2013 is December 31. You have a little longer to propose papers for the Gödel Prize 2013 (deadline for nomination: 11 January 2013), which is jointly awarded with SIGACT.

I hope that you will take the time to send in nominations for those awards and to honour the work of some of the many outstanding researchers in TCS.

Xavier Leroy Receives Microsoft Research: 2012 Verified Software Milestone Award

Xavier Leroy of the Paris-Rocquencourt research center of INRIA, France, is the recipient of the 2012 Microsoft Research Verified Software Milestone Award. The award is given in recognition of Xavier's role as architect of the CompCert C Verified Compiler as well as his leadership of the development team.

The formal presentation of the Award will be made to Xavier at POPL 2013, which will take place in Rome, January 23-25, 2013.

The full award citation can be accessed here.  Its executive summary reads: 

"Microsoft Research is delighted to celebrate the advances made by Dr Leroy in the vital field of software verification. Compilers are the basis for all the software we generate, and by ruling out compiler-introduced bugs, the CompCert project has taken a huge leap in producing strengthening guarantees for reliable critical embedded software across platforms. We congratulate Dr Leroy on his significant achievement in winning this Award." 

Congratulations to Xavier for this  important recognition of his long-term work on CompCert.

Monday, November 12, 2012

Call for post-doctoral research positions at the Warsaw Center of Mathematics and Computer Science

I just received this call from Bartek Klin. Since it might be of interest to readers of this blog, I decided to post it. Warsaw is a hotbed for TCS research. Follow the links below for more details.


Call for post-doctoral research positions at the Warsaw Center of Mathematics and Computer Science.

Warsaw Center of Mathematics and Computer Science (WCMCS) is a joint project of two scientific units: the Faculty of Mathematics, Informatics and Mechanics of the University of Warsaw (MIMUW), and the Institute of Mathematics of the Polish Academy of Sciences (IMPAN). The Center is built on the long-standing cooperation between the two units, in both teaching and research. The Center was designated as a Leading National Research Center (Krajowy Naukowy Osrodek Wiodacy, KNOW) by the Polish Ministry of Science and Higher Education in July 2012. The award comes with a substantial grant which will provide financing of the Center for the next five years. The grant will be used for enhancing the research potential of both participating institutions; this includes financing post-doctoral positions.

The post-doctoral research positions at the WCMCS are aimed at young researchers who have just received their PhD. Successful candidates will be employed as an adiunkt (assistant professor) at one of the following institutions, as indicated in the candidate’s application:
* the Faculty of Mathematics, Informatics and Mechanics at the University
of Warsaw,; or
* the Warsaw branch of the Mathematical Institute of the Polish Academy of

The positions are for 6-12 months, with a possible extension to at most 18 months, altogether. The salary will be 7000 PLN per month, before taxes. In addition, the holder of the position will be eligible for financial support to participate in scientific meetings.

The position comes with a teaching load of up to 60 hours per semester. At least 3/4 of the position’s duration should be between October 1 and June 30.

The applicant should have defended their PhD not earlier than 4 years before the planned beginning of the position. This period can be prolonged by the parental leave.

The candidate applying for a post-doc position at the WCMCS should submit the following documents:
* a cover letter of application addressed to the Board of WCMCS,
indicating the institution (MIMUW or IMPAN) and the period of his/her
* a CV including a list of publications, and copies of 5 best papers, at
* a document that confirms holding the PhD Degree or information about the
expected date of obtaining such a degree,
* a research plan including a collaboration scheme with researchers from

All documents should be sent as pdf files to the following e-mail address: In addition, the applicant should ask at most two senior researchers to send their letters of support to the same e-mail address. The deadline for application is December 10, 2012.

A successful candidate can take his or her job immediately after the announcement of the results of the selection and not later than 8 months after that moment. If the candidate has no PhD degree while submitting, before starting the work he or she should present a document that confirms holding the degree.

More information about WCMCS at

Friday, November 09, 2012

Jean van Heijenoort: Kaleidoscope

Yesterday, an email message on the FOM mailing list alerted me to the availability of a special issue of the journal Logica Universalis in celebration of the centenary of the birth of Jean van Heijenoort. I could not resist reading the contribution entitled Jean van Heijenoort: Kaleidoscope by  Anita Burdman Feferman. This 15-page piece is a wonderful read and paints the picture of a personality who must have been truly (much) larger than life. How often does one meet a logician who was a personal secretary to Leon Trotsky from 1932 to 1939, and from then until 1947, an American Trotskyist activist? Not to mention that he also had a love affair with Frida Kahlo to boot and that he was killed by his wife in an act of passion.

The book Politics, Logic, Love: The Life of Jean van Heijenoort by
Anita Burdman Feferman is now firmly on my list of things to read. (You can read a review here.)

Wednesday, November 07, 2012

Guide for Application to Obtain an Italian National Scientific Qualification

The new recruiting process for  full and associate professor positions in Italian universities is based on a two phase process. Candidates must first obtain the so-called Abilitazione, and then apply for a position at an Italian university. See here for more details.

In order to facilitate international participation in the first stage of this process, the University of Rome "La Sapienza" has created a guide and a series of video tutorials to help researchers who are not fluent in Italian or familiar with Italian rules apply.

For what they are worth (i.e. nothing), here are two considerations off the top of my head. 
  1. First of all, kudos go to "La Sapienza" for producing this supporting material. I am not aware of other Italian institutions that are taking this step and/or who have search committees that are actively looking for foreign applicants. (If you are, please post a comment.)
  2. There is probably something not quite right with a system that needs to be explained using four videos on YouTube :-)
Having said so, I sincerely hope that this new Italian process for recruiting university professors, based on scientific qualification criteria, will help the top Italian CS departments to become even stronger than they already are and that it will offer a ray of hope to young Italian academics. It will also be interesting to see how many non-Italians will apply for the abilitazione. 

Friday, October 26, 2012

Call for nominations: Gödel Prize 2013

The Call for Nominations for the 2013 Gödel Prize has been posted (pdf). Nominations for the award should be submitted to the Chair of the Award Committee, Sanjeev Arora - The deadline for nominations is January 11, 2013.

Any research paper or series of papers by a single author or by a team of authors is deemed eligible if
  • the paper was published in a recognized refereed journal no later than December 31, 2012;
  • the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2000.
The Award Committee consists of  Krzysztof R. Apt (CWI Amsterdam and University of Amsterdam), Sanjeev Arora, Chair (Princeton University), Josep Díaz (Universitat Politècnica de Catalunya), Giuseppe Italiano (Università di Roma Tor Vergata), Daniel Spielman (Yale University), and Éva Tardos (Cornell University). On behalf of the TCS community, I thank the committee members for their important service.

Let me close with a message to the "volume B community". Perhaps the logic/semantics/programming languages community should think strategically, look at the most prominent journal papers meeting the eligibility requirements and drum up the strongest possible support for those. Feel free to look at your crystal ball and suggest candidates for nomination using comments to this post.

As the new president of the EATCS until ICALP 2014, I am taking a sabbatical from issuing nominations in order to avoid any possible conflict of interest.

Wednesday, October 24, 2012

John Cleese on creativity

Recently, I posted a link to a lecture on creativity in computer science by one of my PhD students. After having done so, I was struck by the thought that, at some point, I had watched an excellent, and very funny, lecture by John Cleese on creativity. Here it is, in case any of my readers wants to have a look.

Call for nominations: Presburger Award 2013

The call for nominations for the EATCS Presburger Award 2013 is out. The Presburger Award is given to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers.

Scientists nominated for the award have to be at most 35 years old at the time of the deadline of nomination, which is the 31st of December 2012. This means that  the date of birth of researchers nominated for the Presburger Award 2013 should be in 1977 or later.

The award committee for 2013 consists of Monika Henzinger (chair), Antonin Kucera (who is one of the vice-presidents of the EATCS) and Peter Widmayer.

I hope that you will sharpen your pencils and nominate your favourite young TCS researcher for this award.

Tuesday, October 23, 2012

Call for nominations: EATCS Award 2013

The call for nominations for the EATCS Award 2013 is about to be published officially. However, you can already see it here.

I hope that you will consider submitting a nomination. There are many colleagues out there who would be worthy of this honour, but they can only receive the award if someone nominates them. (I know that this is a triviality, but sometimes people do not send in nominations for their favourite candidates and then wonder why they did not get the prize :-))

Expect more calls for nominations over the next few days.

Friday, October 19, 2012

Lecture on creativity by one of my PhD students

Last week, Eugen-Ioan Goriac, who is a third-year PhD student of mine, delivered a lecture on creativity as part of the Research Methodology course that I am running at Reykjavik University.

Eugen has made a video of his lecture available on YouTube. Here it is, in case it might be of interest to some of my readers.

Enjoy it!

Wednesday, October 17, 2012

The Feit-Thompson theorem checked in Coq!

The Feit-Thompson Theorem  is a key result in the theory of finite groups. Its original proof is 255 pages long and is perhaps the first example of a very long and highly complex proof in group theory.

At 5:46 p.m. on September 20, Georges Gonthier sent an email to his colleagues at the Microsoft Research-Inria Joint Centre in Paris announcing the completion of a six-year effort to prove the Feit-Thompson Theorem in the Coq proof assistant. The mail read, in full: “This is really the End.”

You can read more about this work here and here

Congratulations to Georges and his coworkers on this monumental achievement!

Thursday, September 06, 2012

Invitation to becoming a member of the Italian Committees for professorships

The letter below will be sent to some mailing lists soon. I am posting it here since it is in the interests of the TCS community as a whole to be well represented in this exercise. Despite being amongst the signatories of this letter, I have no academic position in Italy. I am simply an interested observer of academic life in my home country.

Dear colleagues,

The recruitment system for academic staff at Italian universities has recently been changed. The new procedure requires that academics attain the so-called National Scientific Qualification in order to take up a position in an Italian university at the level of associate or full professor. The qualification is granted by National Committees, one for each group of disciplines. All committees are made up of five members, four affiliated to Italian universities and one affiliated to a foreign university located in an OECD country. Members from foreign universities must hold a position equivalent to that of a full professor.

We think that it would be very useful for our research community if you submitted a candidacy to become a foreign member of the National Committee. If you are interested in doing so, you can register your candidacy at

by September 24.

To submit your candidacy, you will have to include a curriculum vitae, the list of scientific publications, the selected disciplinary fields, the number of citations received by your work and your h-index. As part of this process, you will be asked to select one or more Italian Scientific fields from a scroll-down menu (choose at least 01/B1 - Informatics) and some ERC Scientific fields. (There is a scroll-down menu for that too.)

Based on this information, the Italian national agency for the evaluation of universities and research Institutes (ANVUR) will select at least four possible foreign members for each scientific group. The foreign member of each committee will then be randomly selected among those in the lists. The committee will be in service for two years, during which two rounds of evaluations will be carried out. Names and CVs of the selected candidates will be published on the ANVUR website. Members of the evaluation groups will receive an honorarium of 16,000 € for the whole period, plus expenses.

We hope that you will consider submitting your candidacy.

All the best,
Luca Aceto, Rocco De Nicola, Mariangiola Dezani-Ciancaglini

Wednesday, August 15, 2012

Research Methodology in Computer Science

Our autumn semester starts on Monday and I will be teaching the Research Methodology course for master students in computer science and software engineering. This is a 15-week course and I am looking forward to the challenge of keeping the students interested and busy over 30 course sessions. (I have taught short courses on this topic at master and PhD level at different institutions, but this is a substantially larger endeavour.)

At the end of the course, my students are expected to be able to
  • Explain research, research methodologies, and research in Computer Science; 
  • Select a research subject and conduct a research project;  
  • Write technical reports, papers, theses, and proposals effectively;  
  • Give good presentations;  
  • Read and review a technical paper properly; 
  • Explain professional ethics: allocation of credit, authorship issues, conflict of interest and misconduct in science.
I am compiling a list of resources available on the web related to these aspects of our job and will make them available in due course. What publicly available presentations, videos and essays would you recommend that I include? Are there any courses similar to this one that you think I should look at?

Thursday, July 26, 2012

CadiaPlayer GGP Champion Again!

I am proud to announce that the general-game-playing agent CadiaPlayer, developed at my own department by Yngvi Björnsson, Hilmar Finnsson, Stefán Freyr Guðmundsson and Stephan Schiffel, won this year's General Game Playing competition hosted at the AAAI conference, thereby reclaiming the title it lost in 2009.  On its road to the title it defeated among others the winners from the previous two years. As a winner of the competition CadiaPlayer also played an exhibition match consisting of three games against a human player --- Chris Welty from IBM --- and won convincingly.

With this title CadiaPlayer has become the most victorious GGP agent ever, and the only agent so far to win the competition three times.

Congratulation to the CadiaPlayer team!

Tuesday, July 24, 2012

PhD positions at IMT Lucca (reprise)

I am happy to post a revised version of the call for PhD positions at IMT Lucca that I received today from Alberto Lluch Lafuente and Rocco De Nicola. Distribute the announcement as you see fit.

The Institute for Advanced Studies IMT Lucca - Italy ( announces 36 PhD scholarships providing about €13,600 EUR gross yearly plus accommodation and full board. Deadline for application is September 26, 2012.

IMT Lucca (Italy) is an Institute for Advanced Studies and an International Graduate School that acts as a research university with the aim of forming human capital in disciplines characterized by their high potential for concrete application. IMT strives to reach the fusion of theoretical comprehension and practical relevance.

PhD programs are taught exclusively in English. The PhD Program includes a Track in Computer, Decision and Systems Science with a specific Curriculum in Computer Science. The track is coordinated by Rocco De Nicola and aims at preparing researchers and professionals with a wide knowledge of the theoretical foundations of computer science and informatics, control systems and optimization, image analysis, and management science.

The curriculum in Computer Science focuses on languages, models, algorithms, and verification methods for modern distributed systems. PhD students following the curriculum in Computer Science will perform their activities in collaboration with the SysMA research unit ( on system modelling and analysis. This research unit focuses on formal languages, models, methodologies and tools to support the development of correct software systems with high quality in terms of predictability, security, efficiency, usability, re-usability, maintainability, and modularity.

We hope that you might consider applying

If you are not personally interested, please help us signaling these opportunities to colleagues and collaborators. For further information please contact Alberto Lluch Lafuente or Rocco De Nicola.

Friday, July 20, 2012

Samson Abramsky discusses the legacy of Turing

Readers of this blog might be interested in this podcast by the Royal Society in which Samson Abramsky discusses the legacy of Turing. Samson is one of the editors of The foundations of computation, physics and mentality: the Turing legacy, a special issue of Philosophical Transactions of the Royal Society A devoted to "the richness of Alan Turing’s intellectual legacy in the modern conception of computation."


Wednesday, July 18, 2012

Random thoughts on conference presentations

  1. When giving an invited talk at a general TCS conference, do not assume that everyone in the audience is interested in the technicalities of your subject. Focus on the main message, tell the story of the ideas and why you think they are important. Give everyone something to take home. 
  2. Do not assume that you do not need to introduce the setting for your work because someone else has done it before or on an earlier conference day. Not everyone will have attended the talks where the background and motivation were presented.
  3. Do not run over time.
  4. Never speak with your hands on your mouth, even if it feels good :-)
  5. Do not let your voice drop to an inaudible level as your sentence progresses. Dare to speak slowly and loudly.
  6. Ask yourself: How many slides do I really need for a 20-minute talk? Most of us will only use a few, and those should convey the message of the talk at a suitable level of abstraction.
The advice we give others is the advice we ourselves need.

Monday, July 16, 2012

ICALP 2012: Days 3-5

At long last, here are some of my notes from the main events that took place during the last three days of ICALP 2012. There were several excellent talks at Track B (which is the one I attended) and I hope to find the time to discuss some of my favourite papers at some point.

Day 3 was given the best of starts by Gilles Dowek's invited talk entitled A theory independent Curry-de Bruijn-Howard isomorphism. (The slides are here and the abstract is here.) IMHO, Gilles pitched his talk at precisely the right level for a general conference in TCS like ICALP and my impression was that he gave each attendee something to take home, regardless of their area of expertise.

Gilles introduced the seminal Curry-de Bruijn-Howard isomorphism, which was in fact originally proposed by Brouwer, Heyting, and Kolmogorov, who suggested to de fine constructive proofs as algorithms. He surveyed the principles behind the plethora of existing proof processing systems and the principles that led to the development of the universal proof checker Dedukti. Oversimpliying, Dedukti is based on what Gilles called Hilbert and Ackermann’s paradise: one logic and many theories. The logic is the lambda-Pi-calculus proposed by Harper, Honsell and Plotkin. However, theories are represented using rewrite systems, rather than using axioms. Indeed, according to Gilles, "Axioms suck!" (from the point of view of efficiency).

Overall, I enjoyed the talk by Gilles a lot. It was a pity that it was not as well attended as it should have been.

At the start of day 4, Dan Spielman gave an excellent talk on using graph theory to solve linear equations. The talk was entitled Algorithms, Graph Theory, and the Solution of Laplacian Linear Equation and the Laplacian was the main character in the story that Dan recounted with verve and clarity. For further reading on this topic, Dan himself suggested this article by Erica Klarreich at the Simon's Foundation. In passing, Dan also described a method for obtaining "obscenely accurate solutions to a problem by solving a simpler one". 

I had had the pleasure to hear Dan deliver a talk on smoothed analysis when he was a co-recipient of the Gödel Prize 2008 in Reykjavík and I watched the video of his talk at the latest ICM. IMHO, the invited talk at ICALP 2012 confirmed him yet again as one of the very best speakers around. 

Day 4 at ICALP 2012 was also devoted to the awards of the Gödel Prize 2012 and of the EATCS Award. As you surely know already, the Gödel Prize went to three seminal papers in the field of Algorithmic Game Theory. Christos Papadimitriou delivered a talk on behalf of the recipients of the Gödel Prize, who were all . present at the conference apart from Noam Nisam. Christos explained the intellectual roots of the concept now known as the price of anarchy and of algorithmic mechanism design. Moreover, he asked the question: What makes an idea spread? His answer was that an idea spreads if it gives young researchers an opportunity to show how smart they are! 

Christos concluded his talk by being a prophet of doom. (I am using his own words here.) He reminded the people in the audience that, for people like me, the "Hello World" program was Max, a program for finding the largest entry in an array of integers, say. The world has changed. Computation has changed. The inputs to our programs are selfish agents who are interested in the outcome of our computation. Vickrey is the new Max :-)

The EATCS Award went to Moshe Vardi (laudatio), who delivered a presentation entitled  A Logical Revolution. In the talk, Moshe described how logic has one from irrelevance to relevance in our field. The key lessons in this rise of logic are the importance of algorithms, heuristics and tools. One of the key insights is that one should not be scared of worst-case complexity: It always barks, but it does not always bite! Efficient in the field of logic in computer science means exponential. "Exponential is the new polynomial." 

Both award presentations were excellent and were given a long round of applause from a packed audience. 

The last invited talk at ICALP 2012 was delivered by Kohei Honda. Kohei´s talk was entitled Session types and distributed computing. It described the origins of the notion of session type and how sessions types find application in the NSF Ocean Observation Initiative. This represents one of the most impressive applications of notions from concurrency theory outside computer science. Kohei is also one of the prime movers behind the programming language Scribble. His talk was a fitting finale to an excellent ICALP conference.

Thanks again to Artur Czumaj and his team for arranging an excellent conference in the beautiful setting of the University of Warwick.

Thursday, July 12, 2012

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. 

Thursday, June 28, 2012

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:
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!

Thursday, June 07, 2012

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!

Saturday, May 26, 2012

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:
The best student papers are:
Congratulations to all the award recipients!

The scientific programme for ICALP 2012 looks really action packed. The invited speakers are:
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.
The main conference will be preceded by a series of workshops taking place on Sunday, July 8.

Thursday, April 26, 2012

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.

Monday, April 23, 2012

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! 

Thursday, April 12, 2012

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:

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?

Wednesday, April 04, 2012

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:

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:

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 ........

Monday, April 02, 2012

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?

Wednesday, March 21, 2012

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.

Sunday, March 18, 2012

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.

Saturday, March 17, 2012

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.

Thursday, March 08, 2012

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. 

Sunday, February 26, 2012

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

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
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).
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 (, 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.
for more information about living in Camerino.

Friday, February 24, 2012

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:

Deadline is May 15th 2012.

Visit the Institute on YouTube (

Thursday, February 23, 2012

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.

Tuesday, February 14, 2012

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.

Sunday, January 15, 2012

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?