Royal Pardon for Alan Turing

From S. Barry Cooper, here is an official release with the details of the Royal Pardon for Alan Turing, embargoed until 00:01 this morning. Season greetings to all my readers.

PARDON FOR WW2 CODE-BREAKER TURING

By Jamie Grierson, Press Association Home Affairs Correspondent

Second World War code-breaker Alan Turing has been given a posthumous
royal pardon for a 61-year-old conviction for homosexual activity. Dr
Turing, who was pivotal in breaking the Enigma code, arguably shortening
the Second World War by at least two years, was chemically castrated
following his conviction in 1952.

His conviction for "gross indecency" led to the removal of his security
clearance and meant he was no longer able to work for Government
Communications Headquarters (GCHQ) where he had continued to work
following service at Bletchley Park during the war.

Dr Turing, who died aged 41 in 1954 and is often described as the father
of modern computing, has been granted a pardon under the Royal Prerogative
of Mercy by the Queen following a request from Justice Secretary Chris
Grayling. "Dr Alan Turing was an exceptional man with a brilliant mind,"
Mr Grayling said.

"His brilliance was put into practice at Bletchley Park during the Second
World War where he was pivotal to breaking the Enigma code, helping to end
the war and save thousands of lives.

"His later life was overshadowed by his conviction for homosexual
activity, a sentence we would now consider unjust and discriminatory and
which has now been repealed.

"Dr Turing deserves to be remembered and recognised for his fantastic
contribution to the war effort and his legacy to science. A pardon from
the Queen is a fitting tribute to an exceptional man."

Dr Turing died of cyanide poisoning and an inquest recorded a verdict of
suicide, although his mother and others maintained his death was
accidental.

There has been a long campaign to clear the mathematician's name,
including a well-supported e- petition and private member's bill, along
with support from leading scientists such as Sir Stephen Hawking.

The pardon under the Royal Prerogative of Mercy will come into effect
today. The Justice Secretary has the power to ask the Queen to grant a
pardon under the Royal Prerogative of Mercy, for civilians convicted in
England and Wales.

A pardon is only normally granted when the person is innocent of the
offence and where a request has been made by someone with a vested
interest such as a family member. But on this occasion a pardon has been
issued without either requirement being met.

In September 2009, then-prime minister Gordon Brown apologised to Dr
Turing for prosecuting him as a homosexual after a petition calling for
such a move.

An e-petiton - titled "Grant a pardon to Alan Turing" - received 37,404
signatures when it closed in November last year. The request was declined
by Lord McNally on the grounds that Dr Turing was properly convicted of
what at the time was a criminal offence.

Job Ad: Dean of the School of Computer Science at Reykjavik University

The School of Computer Science at Reykjavik University, where I have been working for about nine years now, is looking for a new dean. I append the official job ad, which is being posted on several mailing lists, in the hope that highly-qualified computer scientists will be enticed to apply, despite the short deadline (January 9th, 2014). 

Interested people might want to have a look at the profile of the faculty within the school and at the research centres that it hosts.

Feel free to spread this ad as you see fit.

Dean of School of Computer Science

Reykjavik University seeks an ambitious leader to carry on the development of a growing School of Computer Science. The dean is responsible for administrative affairs as well as for leading the faculty's academic agenda. The dean reports to the Rector of Reykjavik University and is a member of the university‘s executive committee.

We seek candidates that have:

• Strong strategic vision and the ability to shape and lead a team of faculty members and staff

• Doctorate in computer science or related subjects

• Academic teaching and research experience

• Management, operations and leadership experience

• Experience from industry or collaborations with industry

• International experience

Reykjavik University‘s School of Computer Science provides education and research in computer science. The school offers BSc, MSc and PhD degrees and has a leading role in research.  External accreditation committee for doctorate studies claimed the school to be the strongest in Iceland and leading in research.  (PDF file)http://www.ru.is/media/td/SCS_accreditation.pdf   The school has about 900 enrolled students and nearly 30 faculty members.
For further information, please contact Ari Kristinn Jónsson, rector (ari@ru.is), tel: +354-599-6200.
Applications should be submitted before January 9th, 2014, through our applications website:  http://en.ru.is/the-university/open-positions/  or by e-mail at mannaudur@ru.is.
Supplements can be sent to: Reykjavik University, Menntavegur 1, 101 Reykjavík, labeled „Dean's position“. All applications are confidential.
The role of Reykjavik University is to create and disseminate knowledge to enhance the competitiveness and quality of life for individuals and society, guided by good ethics, sustainability and responsibility.
There are four schools within the university; School of Business, School of Computer Science, School of Law and School of Science and Engineering. Education and research at RU are based on strong ties with industry and society. We emphasize interdisciplinary collaboration, international relations and entrepreneurship. Reykjavik University currently has around 3400 students and 250 employees.

Web site for ICALP 2014

The web site for ICALP 2014 is now live. There you will find the call for papers and further details on the conference tracks. The deadline for submitting a paper is February 14, 2014.

October issue of the Bulletin of the EATCS

The October issue  of the EATCS Bulletin is now available online at http://www.eatcs.org/beatcs/index.php/beatcs/issue/view/10. You can download a pdf with the printed version of the Bulletin from http://www.eatcs.org/images/bulletin/beatcs111.pdf. 

This is issue number 111 of the BEATCS and is the first one edited by Kazuo Iwama, the new editor in chief of the EATCS. Apart from four  EATCS columns, including the first one edited by Giovanni Pighizzini, this issue of the Bulletin also features contributions by Erik Demaine (recipient of the Presburger Award 2013), by Luca Moscardelli (recipient of the first Young Researcher in Theoretical Computer Science Award of the Italian Chapter of the EATCS) as well as by Jacopo Mauro and Alessandra Scafuro (recipients of the two Best Italian Ph.D. Thesis in Theoretical Computer Science Awards for 2013 of the Italian Chapter of the EATCS). And I have not yet mentioned the conference reports and the contributions related to EATCS matters, amongst which the calls for nominations for several EATCS awards and fellowships.

I hope that you will enjoy this issue of the Bulletin. Of course, Kazuo and I welcome suggestions for improving the BEATCS. Feel free to drop us a line with your ideas and desiderata.

Call for Nominations: The EATCS-IPEC Nerode Prize 2014 for outstanding papers in multivariate algorithmics

The call for nominations for the EATCS-IPEC Nerode Prize 2014 for outstanding papers in multivariate algorithmics is out. The award committee consists of Georg Gottlob (Oxford University), Jan Arne Telle (University of Bergen) and Peter Widmayer (ETH Zurich, chair). Do make their job hard by nominating your favourite eligible papers!

Turing Machine Opera by Helsinki Skaala Opera

The full show can be watched by starting from this link.

ERC Advanced Grants to TCS researchers

A couple of days ago, the ERC announced that, in its sixth and last Advanced  Grant competition under the EU's Seventh Research Framework Programme, it is awarding over €660 million to 284 senior research leaders. TCS folks will be happy to hear that the following colleagues of ours have been awarded ERC Advanced Grants:

• Monika Henzinger. Challenges in Graph Algorithms with Applications.
• Rachid Guerraoui. Adversary-Oriented Computing.
• Pavel Pudlak. Feasibility, logic and randomness in computational complexity.
• Jean-Daniel Boissonnat. Algorithmic Foundations of Geometry Understanding in Higher Dimensions.
• David Pointcheval. Cryptography for the Cloud.
• Nello Cristianini. Patterns in Big Data: Methods, Applications and Implications. 
• Leslie Ann Goldberg. Mapping the Complexity of Counting.

Congratulations to the award recipients! I am sure that, with the support of the ERC, they will advance the state of the art in their respective fields of interest, benefiting TCS as a whole.

Addendum: As kindly pointed out by anonymous commenters, I have failed to mention that Nati Linial received an ERC Advanced Grant for the project High-dimensional combinatorics and that Lex Schrijver got one for Applying Fundamental Mathematics in Discrete Mathematics, Optimization, and Algorithmics. These two grants are in the field of mathematics, as is the one awarded to Saharon Shelah for the project Model theory and its applications: dependent classes.

Call for Nominations for the Presburger Award 2014

Presburger Award for Young Scientists 2014 

CALL FOR NOMINATIONS 

Deadline: December 31st, 2013

Starting in 2010, the European Association for Theoretical Computer Science (EATCS) established the Presburger Award. The Award is conferred annually at the International Colloquium on Automata, Languages and Programming (ICALP) 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. The Award is named after Mojzesz Presburger who accomplished his path-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929.

Nominations for the Presburger Award can be submitted by any member or group of members of the theoretical computer science community except the nominee and his/her advisors for the master thesis and the doctoral dissertation. Nominated scientists have to be at most 35 years at the time of the deadline of nomination (i.e., for the Presburger Award of 2014 the date of birth should be in 1978 or later).

The Presburger Award Committee of 2014 consists of Antonin Kucera (Brno, chair), Claire Mathieu (Paris), and Peter Widmayer (Zurich). Nominations, consisting of a two page justification and (links to) the respective papers, as well as additional supporting letters, should be sent by e-mail to:

Antonin Kucera
kucera@fi.muni.cz

The subject line of every nomination should start with "Presburger Award 2014", and the message must be received before December 31st, 2013.

The award includes an amount of 1000 Euro and an invitation to ICALP 2014 for a lecture. The Presburger Award is sponsored by CWI, Centrum Wiskunde & Informatica.

Previous Winners:

• Mikolaj Bojanczyk, 2010 
• Patricia Bouyer-Decitre, 2011 
• Venkatesan Guruswami and Mihai Patrascu, 2012 
• Erik Demaine, 2013 

Official website: http://www.eatcs.org/index.php/presburger

Call for nominations: EATCS Fellows

At its meeting at ICALP 2013 in Riga, the EATCS Council decided to start an EATCS Fellows Programme. The first call for nominations is appended.

I hope that EATCS members will submit strong nominations for consideration by the first EATCS Fellow-Selection Committee, which is chaired by Anca Muscholl. The deadline for nominations is December 31. The EATCS fellows will be announced at ICALP 2014 in Copenhagen.

                                                        
                                                                     
                                             
          CALL FOR NOMINATIONS FOR EATCS FELLOWS 2014
                                                                              
                                             
INSTRUCTIONS:
Please note: all nominees and nominators must be EATCS Members

Submit by December 31 of the current year for Fellow consideration by
email to the EATCS Secretary (secretary@eatcs.org). The subject line
of the email should read "EATCS Fellow Nomination - ".

REQUIREMENTS FOR EATCS NOMINATION:

The EATCS Fellows Program is established by the Association to
recognize outstanding EATCS Members for their scientific achievements
in the field of Theoretical Computer Science. The Fellow status is
conferred by the EATCS Fellows-Selection Committee upon a person
having a track record of intellectual and organizational leadership
within the EATCS community.  Fellows are expected to be “model
citizens” of the TCS community, helping to develop the standing of TCS
beyond the frontiers of the community.

In order to be considered by the EATCS Fellows-Selection Committee,
candidates must be nominated by at least four EATCS Members.  
Please verify your membership at http://www.eatcs.org/.

The EATCS Fellows-Selection Committee consists of 

- Rocco De Nicola (IMT Lucca, Italy) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France, chair)
- Dorothea Wagner (Karlsruhe, Germany)
- Roger Wattenhofer (ETH Zurich, CH)

INSTRUCTIONS:

A nomination should consist of answers to the questions below. It can
be co-signed by several EATCS members. At least two nomination letters 
per candidate are recommended. If you are supporting the
nomination from within the candidate's field of
expertise, it is expected that you will be specific about the
individual's technical contributions.

To be considered, nominations for 2014 must be received by December 31, 2013.

1. Name of candidate
Candidate's current affiliation and position
Candidate's email address, postal address and phone number
Nominator(s) relationship to the candidate

2. Short summary of candidate's accomplishments (citation -- 25 words or less)

3. Candidate's accomplishments: Identify the most important
contributions that qualify the candidate for the rank of EATCS Fellow
according to the following two categories: 

A) Technical achievements
B) Outstanding service to the TCS community

Please limit your comments to at most three pages.

4. Nominator(s):
Name(s)
Affiliation(s), email and postal address(es), phone number(s)

Gödel Prize 2014: Call for Nominations

I should be grateful if you could help disseminate this call for nominations. Feel free to post it on your blogs, send it to your collaborators and your department members, and post it on social networks. 

The Gödel Prize 2014
Call for Nominations

Deadline: January 17, 2014.
The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery, Special Interest Group on Algorithms and Computation Theory (ACM-SIGACT). The award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The 22nd Gödel Prize will be awarded at the 41st ICALP in Copenhagen in July 2014.

The Prize is named in honor of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before von Neumann’s death, in what has become the famous “P versus NP” question. The Prize includes an award of USD 5000.

Award Committee: The winner of the Prize is selected by a committee of six members. The EATCS President and the SIGACT Chair each appoint three members to the committee, to serve staggered three-year terms. The committee is chaired alternately by representatives of EATCS and SIGACT. The 2014 Award Committee consists of Krzysztof Apt (CWI Amsterdam), Giuseppe F. Italiano (Università di Roma Tor Vergata), Joseph Mitchell (State University of New York at Stony Brook), Andrew Pitts (University of Cambridge), Daniel Spielman (Yale
University), and Éva Tardos (Cornell University).

Eligibility: The rules for the 2014 Prize are given below and they supersede any different interpretation of the generic rule to be found on websites of both SIGACT and EATCS. Any research paper or series of papers by a single author or by a team of authors is deemed eligible if

1. the paper was published in a recognized refereed journal no later than December 31, 2013;
2. the main results were not published (in either preliminary or final form) in a journal or conference proceedings before January 1st, 2001.

The research work nominated for the award should be in the area of theoretical computer science. The term “theoretical computer science” is meant to encompass, but is not restricted to, research areas covered by ICALP and STOC. Nominations are encouraged from the broadest spectrum of the theoretical computer science community so as to ensure that potential award winning papers are not overlooked. The Award Committee shall have the ultimate authority to decide whether a particular paper is eligible for the Prize.

Nominations: Nominations for the award should be submitted by email to the Award Committee Chair Giuseppe F. Italiano: goedelprize at gmail dot com

Please make sure that the Subject line of all nominations and related messages begin with Goedel Prize 2014. To be considered, nominations for the 2014 Prize must be received by January 17, 2014.

Any member of the scientific community can make nominations. The Award Committee may actively solicit nominations. A nomination should contain a brief summary of the technical content of the paper(s) and a brief explanation of its significance. A printable copy of the research paper or papers should accompany the nomination. The nomination must state the date and venue of the first conference or workshop publication or state that no such publication has
occurred. The work may be in any language. However, if it is not in English, a more extended summary written in English should be enclosed. To be considered for the award, the paper or series of papers must be recommended by at least two individuals, either in the form of two distinct nominations or one nomination including recommendations from two different people. Additional recommendations may also be enclosed and are generally useful. The Award
Committee encourages recommendation and support letters to be mailed separately, without being necessarily shared with the nominator(s). The rest of the nomination package should be sent in a single email whenever possible. Those intending to submit a nomination should contact the Award Committee Chair by email well in advance. The Chair will answer questions about eligibility, encourage coordination among different nominators for the same paper(s), and also accept informal proposals of potential nominees or tentative offers to prepare formal nominations. The committee maintains a database of past nominations for eligible papers, but fresh nominations for the same papers (especially if they highlight new evidence of impact) are always welcome.

Selection Process: The Award Committee is free to use any other sources of information in addition to the ones mentioned above. It may split the award among multiple papers or declare no winner at all. All matters relating to the selection process left unspecified in this document are left to the discretion of the Award Committee.

EATCS Award 2014: Call for Nominations

The European Association for Theoretical Computer Science (EATCS) annually honours a respected scientist from our community with the prestigious EATCS Distinguished Achievement Award. The award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.

For the EATCS Award 2014, candidates may be nominated to the Award Committee consisting of

• Leslie Ann Goldberg (University of Oxford)
• Kim Guldstrand Larsen (Aalborg University)
• Vladimiro Sassone (University of Southampton)

The deadline for nominations is December 31, 2013. Nominations will be kept strictly confidential. They should include supporting justification and be sent by e-mail to the chair of the EATCS Award Committee:

Leslie Ann Goldberg,
Department of Computer Science,
University of Oxford,
Wolfson Bldg, Parks Rd,
Oxford OX1 3QD United Kingdom
Email: leslie.goldberg@cs.ox.ac.uk

The list of previous recipients of the EATCS Award may be found at http://eatcs.org/index.php/eatcs-award.

The next award will be presented during ICALP 2014, which will be held in the period 7-11 July 2014 in Copenhagen,

Preliminary call for papers for ICALP 2014

The preliminary call for papers for ICALP 2014 is available here. (Warning: it is 19 MB, so don't be surprised if it takes some time to download it.) In case, you do not want to download the file, here is the most relevant information. (In the light of a suggestion in one of the comments to this post, I copy-pasted the whole preliminary CFP below.)

Conference dates: 7-11 July 2014
Submission deadline: 14 Feb. 2014
Notification date: 11 Apr. 2014
Final version due: 28 Apr. 2014
Location: IT University Copenhagen

The PC chairs are Elias Koutsopias (Track A), Javier Esparza (Track B) and Pierre Fraigniaud (Track C).

The invited speakers are

• Sanjeev Arora (Princeton University, USA),
• Maurice Herlihy (Brown University, USA)
• Viktor Kuncak (EPFL, CH), and
• Claire Mathieu (ENS Paris, France).

I hope that you will submit your best work to the conference. There will be a lot going on in Copenhagen in early late June-early July, both scientifically (SEA 2014, SWAT 2014 and ICALP 2014 will all take place one after the other) and culturally.

------------------------ FULL PRELIMINARY CFP -------------

ICALP 2014

7 July – 11 July 2014

IT University of Copenhagen

Preliminary Call for Papers

Invited speakers:

Sanjeev Arora • Maurice Herlihy • Viktor Kuncak • Claire Mathieu

Committees

Track A

Elias Koutsoupias (chair) • Dimitris Achlioptas • Pankaj Agrawal • Nikhil Bansal •

Gerth Stølting Brodal • Jean Cardinal • Ning Chen • Giorgos Christodoulou • Xiaotie Deng • Ilias Diakonikolas • Chaled Elbassioni • Amos Fiat • Leslie Goldberg • Vipul Goyal • Giuseppe Italiano • Marcin Kaminsky • Haim Kaplan • Ioardanis Kerenidis • Anna Karlin • Robert Krauthgamer • James Lee • Ashwin Nayak • Jared Saia • Piotr Sankowski • Maria Serna • Christian Sohler • Ryan Williams

Track B

Javier Esparza (chair) • Paolo Baldan • Michele Boreale • Tomas Brazdil • Véronique Bruyère • Veronique Cortier • Anuj Dawar • Kousha Etessami • Maribel Fernandez • David Frutos Escrig • Pierre Ganty • Peter Habermehl • Manfred Kufleitner • Slawomir Lasota • Oded Maler • Sebastian Maneth • Madhavan Mukund • JensPalsberg • Thomas Schwentick • Sonja Smets • Jiri Srba • Steve Zdancewic

Track C

Pierre Fraigniaud (chair) • Keren Censor-Hillel • Andrea Clementi • Benjamin Doerr • Panagiota Fatourou • Michal Feldman • Antonio Fernández Anta • Leszek Gasieniec • Phillip B. Gibbons • Magnus Halldorsson • Robert Kleinberg • Anne‑Marie Kermarrec• Michal Koucky • Gopal Pandurangan • Boaz Patt-Shamir • Andrea Pietracaprina • Andrea Richa • Luís Rodrigues • Christian Scheideler  •  Jukka Suomela • Philipp Woelfel

Organization

Thore Husfeldt (chair), thore@itu.dk

Important dates

Submission deadline: Friday, 14 February 2014

Author notification: Friday, 11 April 2014

Final manuscript due: Monday, 28 April 201

Publication of the best Italian PhD theses in TCS

The Italian Chapter of the EATCS has reached an agreement with Atlantis Press (an imprint of Springer) for the publication of the best Italian PhD theses in TCS in a  special series. Fabio Mogavero's thesis, awarded last year, is the first volume published under this agreement and can be found here.  The thesis of the other winner from last year, Rossano Venturini, will be released soon.

Jacopo Mauro and Alessandra Scafuro are the two recipients of the Best Italian Ph.D. Thesis in Theoretical Computer Science Award 2013, and their theses will appear in the above-mentioned series in due course.

Congratulations to the above-mentioned young researchers!

Ten truths to assist students in choosing a PhD supervisor

Today, the dean of my school shared a well-written article by Tara Brabazon entitled "10 truths a PhD supervisor will never tell you". Here it is, for your reading pleasure.

The article contains useful advice for postgraduate students who are looking for a suitable supervisors, as well as some priceless quotes. I especially liked these two:

1. "Time is finite. Bureaucracy is infinite."
2. "If the prospective supervisor needs a personality replacement, lacks the life skills to manage a trip to the supermarket or requires electronic tagging so that he (or she) does not sleep with the spouses of colleagues, then make another choice. Supervisors should be functional humans."

The comments to that article offer a valuable counterpoint to the "ten truths" and are well worth reading too.

2013 Edsger W. Dijkstra Prize in Distributed Computing

This is not exactly news since the announcement of the award was made a few days ago and I heard about it already during the ICALP 2013 conference dinner. However, since I have not come across any mention of the 2013 Edsger W. Dijkstra Prize in Distributed Computing on the TCS blogs, let me "announce" that the Dijkstra Prize Committee has selected Nati Linial as the recipient of this year’s Edsger W. Dijkstra Prize in Distributed Computing. The prize is given to him for his outstanding paper

Nati Linial. Locality in Distributed Graph Algorithms. SIAM Journal on Computing, 21(1), pages 193-201, 1992. See also here.

You can read the official award citation here. Congrats to Nati Linial and to the award committee for an excellent choice.

June Issue of the Bulletin of the EATCS

The June 2013 issue of the Bulletin of the EATCS is now available as a single  PDF file and from the open journal system. With this issue, we say goodbye to Maria Serna, who has been the editor in chief of the BEATCS for the last five years, editing 15 issues of the Bulletin. As current president of the EATCS, I warmly thank Maria for all the hard work she has put into the challenging task of editing the BEATCS while taking care of all her other duties. Her efforts were way beyond the call of duty.

From the October 2013 issue, the BEATCS will be edited by Kazuo Iwama. I wish Kazuo the best of luck in this new role and look forward to working with him.

If you have any suggestion on how to improve the quality of the BEATCS even further, feel free to contact Kazuo or me, or simply post your suggestions as comments to this blog post.

EATCS YouTube Channel and Slides for Jon Kleinberg's EATCS Lecture

At long last, the EATCS has a YouTube channel. (Thanks to the EATCS Secretary office in Patras for setting it up and for making us enter the 21st century :-)) In due course, the videos of the invited talks and of the EATCS-Award-2013 presentation by Martin Dyer from ICALP 2013 will be available from that channel. For the moment, you can enjoy Erik Demaine's wonderful Presburger Award 2013 video.

Make sure that you subscribe to the channel to get updates on our postings.

The slides for Jon Kleinberg's inspiring EATCS lecture are available here.  Several people asked me for the slides and Jon agreed to make them public. Thanks Jon!

Conference photos taken at ICALP 2013 can be found here. Enjoy.

CAV Award 2013

The CAV Award for 2013 has been presented to Kim G. Larsen, Paul Pettersson and Wang Yi for their seminal work on Uppaal, which is the foremost tool suite for the verification of real-time systems and the synthesis of real-time controllers. Congratulations to the awardees for receiving this well deserved accolade and to the award committee for making such an excellent choice!

If you are interested in using the tool for research and/or teaching, simply download it and read this tutorial by Frits Vaandrager. You will be up and running in no time. 


Uppaal has its roots in a tool originally developed in Uppsala and described in the conference paper Automatic verification of real-time communicating systems by constraint-solving co-authored by Wang Yi, Paul Pettersson and Mads Daniels (Proceedings of FORTE 1994). Since then, Uppaal has been jointly developed by Kim G. Larsen's research group at Aalborg University and by the group led by Wang Yi at Uppsala University. In this period, Uppaal has become an industrial-strength tool for computer-aided verification of computing systems that has been applied to many case studies by several research groups in academia and industry. The efficiency of its computational engine has been improved greatly by theoretical and practical advances relying on highly non-trivial insights. Moreover, the tool now supports the analysis of quantitative extensions of timed automata, automatic model-based testing of real-time systems and the synthesis of controllers in the context of timed games. It is still under continuous development.

Overall, the Uppaal tool is a real success story for the research community working on automated verification of computer systems. As all long-term research and tool development efforts, the work on Uppaal and its applications is due to many gifted researchers and their students. The CAV Award 2013 cannot recognize them all, but the list of authors of the many papers stemming from the work on UPPAAL gives a hint of the magnitude of the research effort involved in building such a tool over a period of nearly 20 years.

ICALP 2013 (Part 3): Award sessions

The best paper award session at ICALP 2013 was held last Monday before the welcome reception (which included excellent, and plentiful, finger food and wine). Mark Bun, John  Fearnley and Dominik Pajak delivered very good presentations of the award-winning papers. I hope that you will check out their papers. In the case of the paper by Mark and Justin Thaler, you can also read this expository blog post. 

The EATCS Award and the Presburger Award were delivered last Tuesday in a joint ceremony that also included the award of honorary doctorates to Josef Gruska and Juris Hartmanis. (See this earlier post of mine for some more information on the ceremony for the honorary doctorates.)

The master of ceremony for the award session was Paul Spirakis. First Martin Dyer received the EATCS Award from Friedhelm Meyer auf der Heide and delivered a presentation entitled Counting ain't easy. Martin started by citing the following fragment of a rhyme from the Winnie the Pooh books:

Cheers for Pooh!
(For who?)
For Pooh -
(Why, what did he do?)
I thought you knew

He then proceeded to give an accessible historical overview of what he did do, covering essentially all the work mentioned in the laudatio for the award.

Last, but by no means least, Tony Kucera presented the Presburger Award 2013 to Erik Demaine. Unfortunately, Erik could not be with us in Riga, but we had a virtual presentation of the award to him via Skype. Moreover, Erik produced an excellent video of a presentation that we could play and enjoy at the conference. Rather than attempting to summarize Erik's inspirational talk, I will simply limit myself to letting him speak for himself.

ICALP 2013 (Part 2): Invited talks

ICALP 2013 in Riga featured five invited presentations and a special EATCS lecture to celebrate the 40th edition of the ICALP conference.

The scientific program for the conference was preceded by short presentations by the rector of the University of Latvia and by Rusins Freivalds. The rector welcomed the ICALP participants, gave us some interesting information about the University of Latvia and wished us long coffee breaks. Rusins discussed the unity of science, and reminded us that, even at the time of the iron curtain, there was one Computer Science.

The conference proper was kicked off on Monday, 8 July, by an invited talk delivered by the Liverpool-bound Paul Spirakis. Paul's talk was entitled A Guided Tour in Random Intersection Graphs. Random Intersection Graphs are random graphs in which there is a universe M of labels and each one of the vertices selects a random subset of M. Two vertices are connected if, and only if, their corresponding subsets of labels intersect. Random intersection graphs were introduced by M. Karonski, E.R. Sheinerman and K.B. Singer-Cohen and have several applications, as well as a rich theory. Paul's talk provided a survey of the main results on the topic obtained by his research group on combinatorial problems over random intersection graphs, such as independent sets, Hamiltonian cycles, colouring, maximum cliques, expansion and random walks. Paul closed the talk by saying that this model is an excellent area of study for PhD students in TCS.

Tuesday's invited address was delivered by Daniel Marx. Daniel's talk has three chapters (his words) and was entitled The Square Root Phenomenon in Planar Graphs. Its starting point was the observation that most of the classic NP-hard problems remain NP-hard when restricted to planar graphs, and only exponential-time algorithms are known for the exact solution of these planar problems. However, in many cases, the exponential-time algorithms on planar graphs are significantly faster than the algorithms for general graphs: for various problems on planar graphs, one often sees a square root appearing in the exponent of the running time of the best algorithms for their solution. Daniel told his audience that, by now, we have a good understanding of why this square root appears: most of these algorithms rely on the notion of treewidth and its relation to grid minors in planar graphs. Daniel also argued that, under the  Exponential Time Hypothesis, one can show that these algorithms are essentially best possible, and therefore the square root must appear in the running time. 

In passing, Daniel contributed also one paper to ICALP Track A and one to ICALP Track B!

Susanne Albers delivered the invited talk on Wednesday, 10 July, on Recent Advances for a Classical Scheduling Problem. In her talk, Susanne revisited the  classic on-line makespan minimization problem, which has been studied since the 1960s. After presenting the classic results on this problem, starting from Graham's 1966 List algorithm and its competitive analysis, she surveyed recent research on settings in which an online algorithm is given extra information or power while processing a job sequence.

The scientific programme on Thursday, 11 July, started with an invited talk by Orna Kupferman, who gave the only invited address that could be readily classified as belonging to ICALP Track B. Orna's presentation dealt with Formalizing and Reasoning about Quality. Traditionally, formal approaches to the verification of reactive systems are boolean in nature: either a system satisfies its specification or it doesn't. In case a system does not meet its specification, one expects a good verification framework to provide a counter-example, that is, a reason why the system is not correct. Orna and her co-authors have generalized formal specification and verification methods to address the quality of systems. In her talk, Orna introduced the linear temporal logic LTL[F], where F is a set arbitrary functions over the interval [0, 1]. Formulae in LTL[F] are interpreted over computations consisting of sequences of atomic propositions. The satisfaction value of an LTL[F] formula is a number between 0 and 1 that describes how well a computation satisfies a formula. The logic generalizes traditional LTL with the functions in F; examples of functions that might be in F are  the maximum or minimum between the satisfaction values of subformulas (these are the quantitative counterparts of boolean OR and AND, respectively), their product and their average. In her talk, Orna showed us how to generalize classic decision problems in formal methods, such as satisfiability, model checking and synthesis,  to search and optimization problems in the quantitative setting. This is achieved by means of an extension of the automata-theoretic approach to LTL to the setting of LTL[F]. 

Before the conference dinner, Jon Kleinberg delivered  a special EATCS lecture to celebrate the 40th ICALP. Jon gave an inspiring and very articulate talk entitled Algorithms, Networks, and Social Phenomena. The talk discussed the development of computational models for systems involving social networks and large human audiences. In particular, Jon focused on how information spreads through such systems, and the ways in which this spread is affected by the underlying network structure. Jon said a few times that, despite having so much data at our disposal, we still do not understand human behaviour. However, IMHO, the work by Jon and his coworkers is shedding some light on some aspects of our behaviour. 

Peter Widmayer delivered the last invited talk on Friday, 12 July. His presentation was entitled To Be Uncertain Is Uncomfortable, But to Be Certain Is Ridiculous, and was accessible and well paced. The starting point of Peter's talk was a "Socratic dialogue" between a statistical physicist and himself. Traditionally, in combinatorial optimization one assumes that an input instance is given with absolute certainty. The goal is then to find an optimum solution for the given instance. In contrast, as the statistical physicist would argue, input data are in reality uncertain, noisy and inaccurate. As a consequence, an optimum solution to a combinatorial optimization problem might not be meaningful in practice. (For example, the shortest path to our work place we computed yesterday evening might not be usable this morning because of changed traffic conditions.) Peter advocated the development of algorithms that find "meaningful" solutions in the presence of uncertain inputs, proposed an approach towards reaching this goal. and argued that it leads to good solutions in the real world.

Videos of these talks (with the exception of Kleinberg's talk, which, as far as I know, was not recorded) will be available in due course.

ICALP 2013 (Part 1)

ICALP 2013 has just finished. It has been an action packed conference and there has been next to no breathing space. I think that the conference was a great success and the organizers deserve our most heartfelt thanks for all their work.

In case you do not know, the conference has being held in Riga at the University of Latvia. This has been the first time that ICALP has been organized in a country of the former Soviet Union and this was the 40th edition of the ICALP conference. First of all, kudos to the local organizers, who did their very best to make the conference a festive occasion and a very pleasant experience for all the attendees. The city of Riga is very pretty and all ICALP participants had a very warm welcome. The University of Latvia was also enrolling a new batch of students during ICALP and this meant that there was a continuous flow of young and happy-looking people on the university premises. This made the main hall of the university a very lively place to be. We were also blessed with sunny and warm weather, which also helped (especially coming from rainy Iceland).

According to the data presented by Agnis Škuškovniks, on behalf of the organizing committee, to the EATCS council and to the EATCS general assembly, there were 193 registered participants in ICALP 2013, of which 67 are students. Including the local participants, the six invited speakers and the two recipients of the honorary doctorates awarded on Tuesday (Josef Gruska and Juris Hartmanis), 217 people attended ICALP 2013. The pre-conference workshops were attended by 102 participants, which is a very healthy number.

The honorary doctorates were an excellent addition to the standard session devoted to the EATCS Awards. Gruska and Hartmanis delivered lucid and inspirational presentations. It was truly awesome to see Juris Hartmanis deliver an off-the-cuff speech on how he left Latvia and ended up at Cornell as chair of the newly-funded CS department. At 85, he is very articulate and sharp. I had the pleasure of discussing several subjects with him during a very pleasant dinner arranged by the organizers. He is still a truly inspirational figure.

Here are some quick EATCS- and ICALP-related news.

• ICALP 2014 will be held in Copenhagen, Denmark, immediately after SWAT 2013. It will be a four-day ICALP and the general chair for the conference is Thore Husfeldt.
• ICALP 2015 will be held in Kyoto, Japan, and will be co-located with LICS 2015. Kazuo Iwama is the ICALP 2015 general chair. This will be the first ever ICALP outside Europe. 
• The EATCS will soon announce and EATCS Fellows programme. The first deadline for nominations will be at the end of this year and we plan to make the first announcement of fellows at ICALP 2014 in Copenhagen.
• The EATCS will begin a new EATCS Young Researcher School Series from 2014. The first school in the series will be organized by Tony Kucera in a beautiful location in Moravia in late July/early August. The theme of the school will be "Automata, Logic and Games". 
• Orna Kupferman gave a thought-provoking talk on "The Gender Challenge in TCS" at the EATCS General Assembly. It really got the audience thinking about this important matter.

In case you are interested in having a look, the slides I used for the EATCS general assembly, where the above decisions where made or communicated, are here. 

In a subsequent post, which I will write when I get home, I will try to discuss some of the many scientific highlights at ICALP 2013.  

To conclude, at the conference I heard that Paul Spirakis is moving to the University of Liverpool. Good luck to Paul!

Associate and/or assistant professor position in the Language Based Technology section of DTU

I have been asked to advertise this position, which might be of interest to several of my readers and their graduating PhD students/postdocs. 

The Language Based Technology section of DTU Applied Mathematics and Computer Science has a new opening for associate and/or assistant professors.

The date for applictions is on October 1st and full details about the call and how to apply are available at

    http://www.dtu.dk/english/career/7da12e65-dc28-42f6-ad11-6be53914b384.aspx

and more information about the Language Based Technology section is available at

    http://www.compute.dtu.dk/english/research/LBT

We are hoping to attract a brilliant associate or assistant professor to complement our research activities in the

modelling, analysis and realisation of systems using language-based techniques and tools.

Our current expertices include static analysis and model checking and take place in a number of research centres and research projects (MT-LAB, IDEA4CPS, TREsPASS, FutureID, SESAMO, PaPP). 

We are interested in concurrent, distributed and mobile systems where reliability and predictability are essential and hence properties related to safety, security and performance are of key interest; the systems may include considerations of socio-technical nature within Systems of Systems.

YouTube channel for the School of Computer Science at Reykjavik University

The School of Computer Science at Reykjavik University has, at long last, created its own YouTube channel. See https://www.youtube.com/user/rucomputerscience. We are uploading videos of talks from season one of our Pearls of Computation seminar series and from last year's Alan Turing Year events, as well as other material that might be of general interest.

In case you are interested in following the events we organize, I'd be grateful if you could spend approximately 5 seconds to open the page and click "Subscribe". Thanks in advance!

Call for guest bloggers from ICALP 2013

I would like to have some blog coverage for ICALP 2013. If you are attending the 40th ICALP in Riga and you are interested in guest blogging, drop me a line. Ideally, I would like to have a guest blogger for each of the tracks in the conference. You are, of course, also most welcome to blog about the five invited talks and the award ceremonies.

PhD Positions at GSSI L'Aquila, Italy - CALL FOR APPLICATIONS

I have been asked to distribute this call for applications for PhD positions in  a newly founded international PhD School in Italy, the Gran Sasso Science Institute. I hope that you will encourage some of your best students to apply.

------ PhD Positions at GSSI L'Aquila, Italy - CALL FOR APPLICATIONS -------

Dear Colleagues,

I would like to ask for your help in spreading around the call for application for PhD candidates in Computer Science at the Gran Sasso Science Institute (GSSI)

<http://www.gssi.infn.it/index.php/en/announcements-all/400-ph-d-call-forapplications>

We are particularly interested in attracting foreign students. So it would be great if you can deliver this announcement through your emailing lists in your countries.

The deadline for applying to the program is 15th july.

Students will be offered  free housing and meals plus the standard three years PhD grant.  The official language is English.

GSSI is a new initiative that is starting in L'Aquila as a consequence of the redevelopment plan after the earthquake. The school  is  managed by INFN (http://www.infn.it/index.php?lang=en) and will start a PhD program in Computer science that is centered around new generation computing, including distributed, ubiquitous and autonomous systems, with emphasis on three main disciplinary pillars: algorithms, software engineering and specification and analysis.

There will be other three Phd programs offered by GSSI, one concerning urban studies, one in Physics mainly centered around astro-particles phisics because of the proximity with the famous Lab
(http://www.lngs.infn.it/), and another in Mathematics centered around mathematical modeling.

The school is supported by other three Italian already established graduate schools, IMT in Lucca for computer science (www.imtlucca.it<http://www.imtlucca.it/> ), SISSA in Trieste for mathematics and physics
(http://www.sissa.it/), and Scuola Superiore S. Anna in Pisa for urban studies (www.sssup.it <http://www.sssup.it/> ).

Thank you in advance for your attention and your support.

Gödel Prize 2013

As some of you might know already, the Gödel Prize 2013, which is awarded jointly by ACM SIGACT and the EATCS, goes to the authors of the following two papers:

Antoine Joux: A One Round Protocol for Tripartite Diffie-Hellman, J. Cryptology 17(4): 263-276 (2004). (Conference version: ANTS 2000)

Dan Boneh, Matthew K. Franklin: Identity-Based Encryption from the Weil Pairing, SIAM J. Comput. 32(3): 586-615 (2003) . (Conference version: CRYPTO 2001)

for their contributions to cryptographic concepts and schemes that provide greater efficiency, flexibility, and security.  These papers established the field of pairing-based cryptography by supplying a precise definition of the security of this approach, and providing compelling new applications for it.

 

The press release issued by the ACM is available at

www.acm.org/press-room/news-releases/2013/goedel-prize-13/

Congrats to the award recipients.

Videos as (part of the) solution to assignments

Anna and I are running a three-week, intensive, first-year course in which the students use Uppaal to make models of computing systems and games, and to analyze them using the verification capabilities of that excellent tool. The students find it very easy to use the tool, and can start solving modelling and verification problems with it in a jiffy.

One of the groups of students taking the course delivered a neat video with their solution to one of the problems we posed them. It is the first time I ever received a video as part of a student report. I expect that this will be the first of many.

Call for editor in chief of the Bulletin of the EATCS

The leadership of the EATCS has decided to decouple the production of the Bulletin of the EATCS (BEATCS) from its editorship. Starting from the October 2013 issue, the BEATCS will be produced, printed and shipped by our Secretary Office in Greece. We think that this change was overdue, and that it will help us improve both the production and the scientific quality of the BEATCS. From the October 2013 issue, the editor in chief of the BEATCS will focus solely on the scientific content of the Bulletin.

Our colleague Maria Serna has served as editor in chief of the BEATCS for a long time and has many other commitments. Therefore, we feel that the time has come to appoint a new editor, whose job will be to continue improving the quality and the impact of the Bulletin, in cooperation with the Council of the EATCS and following on Maria's footsteps.

We hereby ask you for expressions of interest to the role of editor in chief of the BEATCS. Each expression of interest for the position should be accompanied by a couple of paragraphs describing your vision for the future of the BEATCS. You are also most welcome to propose suitable candidates for the position other than yourselves.

Please send your nominations to me via email by the 30th of April at the latest.

I take this opportunity to offer Maria Serna our heartfelt thanks, on behalf of the EATCS, for all the work that she has done over the years as editor in chief of the Bulletin. We really appreciate the effort she has put into this important service to the EATCS and the TCS community as a whole.

All the best,

Luca Aceto
President of the EATCS

Two Pearls of Computation Talks at Reykjavík University

Season one of the new Pearls of Computation seminar series at Reykjavik University is in full swing.

On Friday, 15 February 2013, my ICE-TCS colleague Eyjólfur Ingi Ásgeirsson (School of Science and Engineering, Reykjavik University) delivered a talk on E.W. Dijkstra entitled The shortest path to beautiful code ( - DEATH TO GOTO - ).

• Recording of the talk (slides and audio) in .avi format.
• Slides with the three "silly games" mentioned in the talk. [Solutions]
• An Interview With Edsger W. Dijkstra by Thomas J. Misa, Communications of the ACM, Vol. 53 No. 8, Pages 41-47.
• E. W. Dijkstra Archive.
• K.R. Apt, Edsger Wybe Dijkstra (1930 -- 2002): A Portrait of a Genius. Formal Aspects of Computing, 14, pp. 92-98, 2002.

The following talk was held on Friday, 5 April 2013, when Kristinn R. Thorisson (School of Computer Science, Reykjavik University) delivered a presentation on the work of Marvin Minsky entitled Marvin Minsky: Pioneer, Critic, Optimist.

• Recording of the talk (slides and audio) in .mp4 format.
• Human Interface video played by Kristinn during the talk.
• NOVA Interview with Marvin Minsky. 

Enjoy!

Best paper awards at ICALP 2013

The best paper awards at ICALP 2013 will go to the following papers:

• Track A: Mark Bun and Justin Thaler. Dual Lower Bounds for Approximate Degree and Markov-Bernstein Inequalities.
• Track B: John Fearnley and Marcin Jurdziński. Reachability in Two-Clock Timed Automata is PSPACE-complete.
  
• Track C: Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Pajak and Przemysław Uznański. Fast Collaborative Graph Exploration. 

The best student paper awards will instead go to:

• Track A: Radu Curticapean. Counting matchings of size k is #W[1]-hard.
• Track B: Nicolas Basset. A maximal entropy stochastic process for a timed automaton. 

None of the accepted papers for Track C was a student paper.

Congratulations to all the recipients of the best paper awards! I look forward to listening to their talks at ICALP 2013. 

Accepted papers at ICALP 2013

The list of accepted papers for ICALP 2013 is now available (with and without abstracts). ICALP 2013 is the 40th  ICALP conference. I hope to see many of you in Riga to celebrate this event.

Faculty Position in Interactive Storytelling and Game Design at Reykjavik University

The School of Computer Science at Reykjavik University seeks to hire a faculty member for a new academic position in the field of interactive narrative and game design. We are interested in an ambitious, highly qualified academic who can combine innovative teaching and cutting-­edge research in the rapidly evolving area of interactive digital entertainment within our school.

The faculty position is funded through a collaboration with massively multiplayer game developer CCP Games Inc.  We are particularly interested in active researchers who see opportunities in breaking new ground with CCP and with existing faculty within Reykjavík University, in particular within CADIA, the school's artificial intelligence research center. CCP will fund the faculty position for a minimum of 5 years; following that period, CCP and Reykjavík University will seek continued funding for the position. Full academic freedom is respected, however, by both CCP and Reykjavík University.

See here for more information. The application deadline is 30 April 2013 and interviews will be held in May 2013.

LICS 2013 Accepted Papers

This is not news anymore, but the list of accepted papers for LICS 2013 is available here.

As usual, the accepted papers look very interesting and I hope to find the time to read several of them when they become available. (This might be wishful thinking. It seems that finding time to read papers is getting harder by the day, alas.)

For what it is worth, here are two papers that immediately caught my attention browsing through the list of accepted papers and that are available on line.

• Dexter Kozen, Kim Guldstrand Larsen, Radu Mardare and Prakash Panangaden. Stone Duality for Markov Processes.
• Mikołaj Bojańczyk, Bartek Klin, Sławomir Lasota and Szymon Toruńczyk. Turing Machines with Atoms. 

To whet your appetite, here is what is probably the main result in the latter paper.

Theorem: In sets with equality atoms, there is a language that is decidable in nondeterministic polynomial time, but not deterministically semi-decidable.

Before you get carried away, here is what the authors write below the statement of this theorem.

A consequence of the theorem is that, with atoms, P is not equal to NP. It is not our intention to play up the significance of this result. In a sense, the theorem is too strong for its own good: it shows that computation with atoms is so different from computation without atoms, that results on the power of nondeterminism in the presence of atoms are unlikely to shed new light on the power of nondeterminism without atoms.

Congratulations to all the authors of accepted papers.

BCS Lovelace Medal to Samson Abramsky

Happy Easter news for the TCS community. Samson Abramsky is being awarded the British Computer Society (BCS) Lovelace Medal for 2013. (The press release is here.) The BCS Lovelace Medal was established in 1998 in honour of Lady Augusta Ada Byron, Countess of Lovelace and daughter of Lord Byron. The Medal is presented annually to individuals who, in the opinion of BCS, have made a significant contribution to the advancement of Information Systems.

Quoting Samson,

It is particularly pleasing that this award recognizes work of a highly foundational character, and shows the commitment of BCS to support the study of computing not only for its manifold applications, but as a fundamental scientific discipline in its own right.

As the press release states, Samson

is pre-eminent in setting the modern agenda in the foundations of computer science, an area where he has made immense contributions since the 1980s. His contributions in each of the past three decades had a major impact on the field, notably: Domain Theory in Logical Form, Game Semantics and Categorical Quantum Mechanics. He has shown the ability to change research fields and to establish new interdisciplinary approaches.  His work over the past decade has shown that methods and concepts developed in theoretical computer science can be applied very directly in quantum information, and the foundations of quantum mechanics itself.

Another recent example of application of methods from "volume B TCS" to other fields is in this short paper, where Samson and Wiktor Winschel apply coalgebraic and other structural methods originating from computer science to economics and game theory.

Congratulations to Samson!

Does it also work in theory?

Courtesy of Robbert Dijkgraaf's media page.

How to write an unsuccessful letter of nomination for an award

The following piece of text has been going through my head since the meeting of an award committee I attended earlier this week. I had to get rid of it by writing it down. So here it is, for your reading pleasure. I thought that it was best to choose a "How to have your abstract rejected" style for this piece.

You have just seen the call for nominations for an award and you have an excellent candidate for this accolade in mind. The call for nominations asks for a letter of nomination and gives some criteria that a nominee for the award should satisfy. How can you increase the chances that your nomination will be unsuccessful? The aim of this short piece is to present some simple approaches that are guaranteed to increase the chances that your nomination will be unsuccessful, even if you were nominating Albert Einstein for the Relativity Award 2013.

The first step in ensuring lack of success of a nomination is not to read the guidelines in the call for nominations. This will make it highly likely that your letter will not address at least some of the criteria that a good nomination should have. However, this leaves open the possibility that, by chance, your letter of nomination address some of the most important criteria for nominating your candidate. The best approach to prevent this from happening is to be systematic. Do read the call for nominations and make sure that you avoid addressing each of the criteria listed there. For example, if the call asks for (a link to) a CV, do not provide any!

However, the systematic approach requires precious time, effort and organization. Isn't there a better way to achieve your goal of submitting an unsuccessful nomination without sweating too much? Indeed there is! The perfect, no-sweat unsuccessful letter of nomination is a one liner that reads:

I nominate X for award Y. Best regards, Z

Submitting this letter template, which you should feel free to reuse, will strongly indicate to the award committee that is in charge of evaluating the nominations and of selecting the award recipient(s)

1. that you really do not know why the nominee deserves the award, and
2. that you are not willing to invest any time and effort in finding out why the nominee is worthy of the honour and in convincing the committee that (s)he is the one to select.
   

Is there a better way of achieving your goal? If so, I should really like to know.

Monotasking vs. multitasking

I am enjoying reading Out of Their Minds (The Lives and Discoveries of 15 Great Computer Scientists) by Dennis Shasha and Cathy Lazere. IMHO, the book does a great job in making the lives and ideas of some of the leaders in our field accessible to a general public. I will recommend it to my students and to the colleagues of mine who will prepare future Pearls of Computation seminars.

At the end of the chapter devoted to Donald E. Knuth,  the authors quote Don Knuth as saying:

I do one thing at a time. This is what computer scientists call batch processing---the alternative is swapping in and out. I do not swap in and out.

This quote reminded me a TED talk, in which Italian designer Paolo Cardini encourages his audience to consider the virtues of monotasking.

For several years in my career, I was largely a monotasking person. In my research, I mostly worked on one thing at the time. However, this has changed substantially over the years.  Now I find myself multitasking and context switching a lot and this leads to more stress at work. I guess that most of us have a similar story to tell; the length of the list of things to do increases much faster than our ability to get things done, alas.

Stephen Cook receives the Gerhard Herzberg Canada Gold Medal for Science and Engineering

Stephen Cook has received Canada's highest honour,  the Gerhard Herzberg Canada Gold Medal for Science and Engineering. More on Stephen Cook's Herzberg Canada Gold Medal can be found here.

EATCS Award 2013 to Martin Dyer

The EATCS Awards Committee, consisting of Leslie Ann Goldberg, Vladimiro Sassone and Friedhelm Meyer auf der Heide (chair), has unanimously decided to give the EATCS Award to Martin Dyer. The laudatio for Martin Dyer is available here. Martin's Wikipedia page mentions his key achievements in

(1) - polynomial time algorithm for approximating the volume of convex bodies (with Alan Frieze and Ravindran Kannan)
(2) - linear programming in fixed dimensions
(3) - the path coupling method for proving mixing of Markov chains (with Russ Bubley)
(4) - complexity of counting constraint satisfaction problems.

In addition, the laudatio singles out his work with Alan Frieze on developing the probabilistic analysis of algorithms. Dyer and Frieze showed that many NP-hard problems arising in combinatorial optimisation can be solved in polynomial expected time when the instances are drawn from natural distributions.

Congratulations to Martin!

Friday Fun

 

Source: One of the Computer Science students at Reykjavík University

Erik Demaine receives the EATCS Presburger Award 2013

The Presburger Award Committee, consisting of Peter Widmayer, Antonin Kucera and Monika Henzinger (chair), has unanimously decided to propose Erik Demaine (MIT, USA) as recipient of the 2013 EATCS Presburger Award for young scientists. Congratulations to Erik!

The Presburger Award is sponsored by CWI, Centrum Wiskunde & Informatica.

The citation for the award reads as follows.

Erik Demaine, born in 1981, has made outstanding contributions in several fields of algorithms, namely computational geometry, data structures, graph algorithms and recreational algorithms. In computational geometry and data structures he has solved or made significant progress on classic problems such as the carpenter’s rule problem, the hinged-dissection problem, the prefix-sum problem, and the dynamic optimality conjecture. In graph algorithms he used the powerful theory of graph minors to develop a suite of algorithms for approximately solving a general family of intractable problems. He also started the new field of computational origami, where his book is the leading authority in the field. His work  has shown promising applications to computer graphics, sensor networks, molecular biology, programmable matter, and manufacturing and engineering.

The committee recommends Erik Demaine as an exceptional young scientist who fully deserves the Presburger Award.

The committee would also like to mention that the quality of all nominations submitted this year was very high. The Presburger Award is attracting the best young scientists in the field of theoretical computer science worldwide.

Addendum, 14 February 2013: Check out a Popular Science article on Erik's work here:  http://www.popsci.com/science/article/2013-01/dazzling-sometimes-absurd-always-playful-genius-erik-demaine.

Poster for the Pearls of Computation seminar series

The poster has been designed by the talented team at Podpunkt. In case you need a good design for book covers, logos or posters, you might wish to consider them. Look at their portfolio and enjoy their work. As I remarked in an earlier post, the Podpunkt studio has strong connections with mathematics and TCS.

ICALP 2013 deadline is two weeks away

The second call for papers for ICALP 2013 is available here. I hope that several readers of this blog will submit some of their best work to the conference. The deadline for submissions is February 15.

This is the 40th ICALP and, in addition to the invited talks and the award addresses, will also feature a special EATCS Lecture by Jon Kleinberg to celebrate this festive occasion.

Pearls of Computation: A new seminar series

This coming Friday I will kick off a new seminar series organized by ICE-TCS at Reykjavik University. The seminar series is called Pearls of Computation and aims at presenting the work of some of the recipients of the ACM Turing Award (or of some other major award related to computer science) in an accessible way. The target audience consists of students in computer science and anyone with a potential interest in the subject. (The inspiration for this seminar series comes from the Pearls of Theory talks that were held at BRICS in Aarhus in a past that looks so far away now.)

We will try to tell the stories behind the scientific contributions of some of the key figures in computer science in a non-technical way, highlighting the context in which they were made, the state of the art at the time, why they are important and what impact they have had. In the process, I believe that both the attendees and the speakers will all learn something new and develop an increased appreciation (and, why not, pride) for the contributions of some of the people who have shaped our field.

My inaugural talk in this series will be devoted to the life and work of Robin Milner (1934-2010), whose work has had a deep and lasting influence on my modest contribution to concurrency theory. The schedule for the talks that will take place this semester is available here.

Jaco de Bakker, 1939-2012

Jaco de Bakker, one of the founding fathers of the EATCS and a prominent Dutch TCS researcher, passed away on December 13, 2013. The following obituary by Jan Bergstra, Jan Willem Klop and Jan Rutten has been circulated recently on the Concurrency mailing list and appears on the web site of the Academia Europaea as well as on the EATCS web site.

On December 13, 2012, our colleague Jacobus Willem (Jaco) de Bakker, member of the Section Informatics of the Academia Europaea since 1990, passed away surrounded by his family in his home in Amsterdam after a short illness. He is survived by his wife Angeline, his children Bas, Jaska, Catrien, Jacob and Lisa, and two grandchildren.

Jaco was born on March 7, 1939, in Ede, the Netherlands. He was for more than 38 years, from 1964 until 2002, connected as Head of the Computer Science Department to the Mathematical Centre, later called CWI  (Centrum Wiskunde & Informatica) in Amsterdam. He was a Fellow of CWI since 2002. In 1973 he was appointed as Professor in Computer Science, in particular for the mathematical semantics of programming languages and reasoning on program correctness, at the VU University Amsterdam, at that time called Vrije Universiteit Amsterdam. He occupied this professorship until his emeritate in 2002. In 1989 he was appointed as a member  of the Royal Netherlands Academy of Arts and Sciences (KNAW), in the Section Mathematics. In 1972, Jaco was one of the founding fathers of the EATCS, the European Association for Theoretical Computer Science; he was Vice-President of the EATCS from 1972 until 1982, and Member of the Board until 1988. Since 1998 he was honorary member of IFIP Working Group 2.2, Formal Description of Programming Concepts. In 2002, during his retirement symposium at CWI, he received the Royal Decoration Knight of the Order of the Lion of the Netherlands (Ridder in de Orde van de Nederlandse Leeuw).

Jaco de Bakker started his scientific career with his Ph.-D. thesis in 1967 at the University of Amsterdam, with promotor Adriaan (Aad) van Wijngaarden, entitled: Formal Definition of Programming Languages: with an Application to the Definition of ALGOL 60. Jaco de Bakker was world-wide known and recognized for his pioneering work in developing the denotational and operational semantics of many basic features in programming languages, in a precise and rigorous mathematical style. One of its highlights became known as
the induction rule of De Bakker and Scott. This culminated in his book Mathematical Theory of Program Correctness (1980). Later on, in the early eighties, he turned to the theory of communicating processes, introduced by Hoare and Milner, a theory known in those days as "concurrency". His initial investigations in this field were in cooperation with Jeffery Zucker. The basic features in this theoretical area were treated in the same mathematically rigorous style in his book Control Flow Semantics (1996) together with Erik
de Vink. Apart from these books, he wrote more than 150 scientific articles.

In the Netherlands Jaco de Bakker was the originator of an extensive school of theoretical computer scientists. He supervised many Ph.D.-theses, and was the driving force in the eighties, together with Willem-Paul de Roever and Grzegorz Rozenberg, behind several nation-wide programmes for research and education in the Netherlands, such as REX (Research and Education in Concurrent Systems). REX lasted from 1988 to 1993; it was preceded by LPC (Landelijk Project Concurrency, National Project Concurrency) from 1984-1988. Prior to these programmes Jaco was Director, together with Jan van Leeuwen, of the 'Advanced Course on Foundations of Computer Science', a biennial series of influential courses with international attendance, from 1974 to 1982, held in Amsterdam. Jaco was also one of the founding fathers in 1979 of the Dutch Association for Theoretical Computer Science (WTI, Werkgemeenschap Theoretische Informatica), since 1995 called NVTI (Nederlandse Vereniging voor Theoretische Informatica). Jaco was Chairman of the WTI from 1979 until 1987. Jaco was proud of the fact that 32 scientists who at some time worked in his group were eventually appointed full professor.

Also in the eighties, Jaco was instrumental in stimulating the involvement and participation of the Dutch research community in the big European computer science frameworks such as FAST, Meteor, ESPRIT (European Programme for Research in Information Technology) and BRA (Basic Research Actions). As Head of the CWI Department Software Engineering he stimulated intensive contacts with the European research community, resulting in a lively and productive research atmosphere in which researchers of many nationalities cooperated on a regular basis.

In addition to playing a crucial role in education and research in theoretical computer science, Jaco de Bakker was also a gifted and respected science director and administrator. He influenced  the lives of many of us. We all remember him as a great scientist and  an amiable person. Moreover many computer scientists will remember him as a friend.

Jan Bergstra, Jan Willem Klop and Jan Rutten