Sunday, March 23, 2014

Contemplate Ltd

These are days in which one of the outcomes of the work academics do, and one of the measures of its impact, is commercial exploitation of research and development carried out within the four walls of the "Ivory Tower". Universities the world over have different approaches towards commercial exploitation of research funding and IP rights and mine is no exception, apart from being a bit late in this game.

A discussion of IP policy issues might be the topic for a future post. Here I will just limit myself to pointing out an excellent example of a spin-off company from the University of Edinburgh, Contemplate Ltd, whose CTO and founder is Don Sannella. (Disclaimer: I have absolutely no connection with Contemplate myself!)

Contemplate was founded to commercialise research on static analysis done at the University of Edinburgh. Its product, ThreadSafe, pinpoints and helps to diagnose the most common and pernicious Java concurrency bugs. Concurrency is essential for high performance and low latency, but concurrent programming is hard to do right and therefore the use of automatic analysis tools should play an important role in the development of parallel software.

ThreadSafe is available as an easy-to-use Eclipse plug-in, which relates bug reports directly to the source code, and also as a SonarQube plugin (for team working). Also, by the end of March, as a command-line tool which generates an HTML report (for use with build tools).

This InfoQ article shows ThreadSafe in action finding concurrency errors in open source applications including Apache JMeter and K9Mail that are not caught by any other Java static analysis tool. 

Free two-week trials are available from Moreover, I understand that the tool will soon be offered with monthly and annual subscriptions.

If you develop concurrent software with Java, I encourage you to try the tool.

Saturday, March 15, 2014

EATCS-IPEC Nerode Prize 2014

The EATCS and IPEC are proud to announce that the Nerode Prize 2014 for outstanding papers in the area of multivariate algorithmics will be awarded to the following two papers:
  • "On problems without polynomial kernels", Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin, Journal of Computer and System Sciences, 2009 and
  • "Infeasibility of instance compression and succinct PCPs for NP", Lance Fortnow, Rahul Santhanam, Journal of Computer and System Sciences, 2011.
Congratulations to all the award recipients!
The presentation of the prize will take place at IPEC 2014, which this year will be organized as part of ALGO 2014 (Wroclaw, Poland, 10-12 September 2014).

The Prize is named in honour of Anil Nerode, in recognition of his major contributions to mathematical logic, theory of automata, computability and complexity theory.

The Nerode Prize 2014 Committee consists of Georg Gottlob (University of Oxford, UK), Jan Arne Telle (University of Bergen, Norway), and Peter Widmayer (ETH Zurich, Switzerland; chair).

Thursday, March 13, 2014

ACM TALG Editor-in-Chief Search: Call for Nominations

Anne Condon asked me to distribute this call. Do consider nominating colleagues for this prestigious position.

Nominations are now open for the next editor-in-chief of the ACM Transactions on Algorithms. ACM TALG (web page: publishes original research of the highest quality dealing with algorithms. It is a peer-reviewed journal, appearing quarterly. Specific areas of computation covered by the journal are listed at

We are looking for a well-established person with a strong record of research achievements and service, and with a vision for the future of the field. The term of appointment is three years, to begin late summer 2014, with the possibility of  renewal for a second term. The editor-in-chief is responsible for faithfully executing the editorial charter of the journal yet should be proactive in
adapting the journal and its charter to changes in the field. A description of the duties of the EiC and evaluation criteria can be found at h ttp://

Professor Valerie King of the University of Victoria, Victoria, BC, Canada is Chair of the Search Committee. All nominees, including self-nominees, should send a CV and a Vision Statement for TALG (at least one page), with subject header “EiC nomination” to:

The deadline for nominations is Friday, May 16, 2014 at 11:59 p.m. (PST).

Wednesday, March 12, 2014

February issue of the BEATCS on line

The 112nd issue of the EATCS Bulletin, is now available online for everyone at

If you prefer, you can download a pdf with the printed version of the bulletin from

Thanks to Efi and Ioannis from our secretary office in Greece for all the work they have done on this issue and to the colleagues who contributed pieces to this issue of the BEATCS.

Readers of TCS blogs might notice that this issue of the BEATCS includes revised versions of two essays by Sanjeev Arora and Boaz Barak that had appeared earlier in Windows on Theory. Thanks to both Boaz and Sanjeev for agreeing to publish their pieces in the BEATCS!

The EATCS Bulletin has been open access for a few years now and we are happy to make it accessible also to interested readers who are not members of the association.

As you can read in my Letter from the President published in this issue, the EATCS has been taking several steps in support of young researchers, in addition to the instruments we had already in place. If you'd like to support these initiatives and forthcoming ones, consider joining the EATCS. The membership fee for one year (two years for young researchers) is 30€ and we offer a joint membership discount with SIGACT.

Tuesday, March 11, 2014

9th SCANDINAVIAN LOGIC SYMPOSIUM: Call for submissions

Various topics in logic in computer science are of interest for this meeting. Consider submitting an abstract!

25-27 August 2014, University of Tampere, Finland


The 9th Scandinavian Logic Symposium will be held at the Museum Centre
Vapriikki in Tampere, Finland, during 25-27 August 2014 under the auspices
of the Scandinavian Logic Society (SLS,

As with previous editions of the Symposium, its primary aims are to
reflect the current activities in logic in the Nordic countries and to
provide a local meeting forum for their logical communities, broadly
conceived. Besides, it invites and warmly welcomes participation of
logicians from all over the world.

The scope of SLS 2014 is broad, ranging over the whole areas of
Mathematical and Philosophical Logic, as well as Logical Methods in
Computer Science, Artificial Intelligence, Linguistics, etc. Major
topics include (but are not limited to): Proof Theory, Constructivism,
Model Theory, Set Theory, Computability Theory, Algebra and Logic,
Categorical Logic, Logic and Computer Science, Logic and Linguistics,
Logic in AI and Multi-Agent Systems, Logics of Games, Modal and other
non-classical Logics, Philosophical Logic.

     Mai Gehrke (LIAFA, Paris)
     Volker Halbach (University of Oxford)
     Asger Törnquist (University of Copenhagen)
Jouko Väänänen (University of Helsinki and University of Amsterdam)
     Thomas Ågotnes (University of Bergen)

     Co-chairs: Sara Negri (University of Helsinki)
and Valentin Goranko (Technical University of Denmark)

     Luca Aceto (Reykjavik University)
     Lars Birkedal (Aarhus University)
     Patrick Blackburn (Roskilde University)
     Patricia Blanchette  (University of Notre Dame, US)
     Thierry Coquand (University of Gothenburg)
     Ali Enayat (University of Gothenburg)
     Øystein Linnebo (University of Oslo and Birkbeck College London)
     Kerkko Luosto (University of Tampere)
     Dag Normann (University of Oslo)
     Gabriel Sandu (University of Helsinki)
     Arild Waaler (University of Oslo)
     Dag Westerståhl (University of Stockholm)

     Chair: Lauri Hella  (University of Tampere)

     Kerkko Luosto (University of Tampere)
     Antti Kuusisto (University of Wroclaw)
     Jonni Virtema (University of Tampere)
     Jevgeni Haigora (University of Tampere)

     Abstracts of contributed talks, in PDF format, not exceeding one A4
     (11pt) page, should be submitted by  April 25, 2014, through
     Abstracts should be typeset following the format of a LaTeX style
file that will be posted on the conference website on March 16.

     Submission deadline: April 25, 2014
     Notification: May 16, 2014
     Final programme: July 25, 2014

Museum Centre Vapriikki is situated on the banks of the Tammmerkoski
It is within a walking distance from the center of Tampere and the railway

     There are several hotels within a walking distance from the conference
     venue. The organizers will provide a list of some alternatives on the
     conference website.

Details concerning registration will be posted soon on the conference

     ENQUIRIES: Write email to

Friday, March 07, 2014

David Woodruff receives the Presburger Award 2014

The EATCS is proud to announce that the Presburger Award 2014 Committee has chosen David Woodruff (IBM Almaden Research Center) as the recipient of the Presburger Award 2014. Congratulations to David!

Since 2010, the Presburger Award has been given each year 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. The Presburger Award 2014 is sponsored by CWI Amsterdam and will be presented at ICALP 2014 in Copenhagen, Denmark.

David Woodruff, born in 1980, has made important contributions to the theory of data streams, both creating new algorithms, and demonstrating that certain algorithms cannot exist. His work has an impact on other fields, including compressed sensing, machine learning, and numerical linear algebra. In the area of data streams, he resolved the Distinct Elements Problem, simultaneously optimizing the amount of memory used, the time needed to process each new entity, and the time needed to report an estimate of the number of distinct elements in the stream. In the area of machine learning, he used his previous results on data streams to design sub-linear algorithms for linear classification and minimum enclosing ball problems. In numerical linear algebra, he developed the first algorithms for low rank approximation and regression that run in time proportional to the number of non-zero entries of the input matrix. His work also resulted in 17 patents related to data streams and their applications.

The 2014 Presburger Award Committee consisted of
Antonin Kucera Brno, chair
Claire Mathieu ENS Paris
Peter Widmayer Zurich

Wednesday, March 05, 2014

EATCS Fellows class of 2014 named

The EATCS has recognized ten of its members for their outstanding contributions to theoretical computer science by naming them as the first recipients of an EATCS fellowship.

The EATCS Fellows for 2014 are:
  • Susanne Albers (Technische Universität München, Germany) for "her contributions to the design and analysis of algorithms, especially online algorithms, approximation algorithms, algorithmic game theory and algorithm engineering";
  • Giorgio Ausiello (Università di Roma "La Sapienza", Italy) for "the impact of his scientific work in the field of algorithms and computational complexity and for his service to the scientific community";
  • the late Wilfried Brauer (Technische Universität München, Germany) for "outstanding contributions to the foundation and organization of the European TCS community";
  • Herbert Edelsbrunner (Institute of Science and Technology Austria and Duke University, USA) for "his tremendous impact on the field of computational geometry";
  • Mike Fellows (Charles Darwin University, Australia) for "his role in founding the field of parameterized complexity theory, which has become a major subfield of research in theoretical computer science, and for being a leader in computer science education";
  • Yuri Gurevich (Microsoft Research, USA) for "his development of abstract state machines and for outstanding contributions to algebra, logic, game theory, complexity theory and  software engineering";
  • Monika Henzinger (University of Vienna, Austria) for "being one of the pioneers of web algorithms, algorithms that deal with problems of the world wide web";
  • Jean-Eric Pin (LIAFA, CNRS and University Paris Diderot, France) for "outstanding contributions to the algebraic theory of automata and languages in connection with logic, topology, and combinatorics and service to the European TCS community";
  • Paul Spirakis (University of Liverpool, UK, and University of Patras, Greece) for "seminal papers on Random Graphs and Population Protocols, Algorithmic Game Theory, as well as Robust Parallel Distribute Computing";
  • Wolfgang Thomas (RWTH Aachen University, Germany) for "foundational  contributions to the development of automata theory as a framework for modelling, analyzing, verifying and synthesizing information processing systems."
The aforementioned members of the EATCS were selected by the EATCS Fellow Selection Committee, after examining the nominations received from our research community. The EATCS Fellow Selection Committee for 2014 consisted of
  • Rocco De Nicola (IMT Lucca, Italy,
  • Paul Goldberg (Oxford, UK),
  • Anca Muscholl (Bordeaux, France; chair),
  • Dorothea Wagner (Karlsruhe, Germany) and
  • Roger Wattenhofer (ETH Zurich, CH)
The EATCS Fellows Program was established by the association last year  to recognize outstanding EACTS members for their scientific achievements in the field of Theoretical Computer Science. The EATCS is very proud to have the above-mentioned members of the organization as its first fellows. Congratulations all of them!