27th Nordic Workshop on Programming Theory

The 27th Nordic Workshop on Programming Theory (NWPT 2015) was held at Reykjavik University in the period 21-23 October and was organized by AnnaIngolfsdottir and me in cooperation with our postdocs  Dario Della Monica, Ignacio Fabregas and Alvaro Garcia Perez. It finished on Friday, 23 October,  at around 17:30 after three packed days of scientific presentations.

The workshop had 57 registered participants (50 of which came from abroad, giving yet another indication of the powerful lure of Iceland as a destination for scientific events), and several talks were also attended by some local faculty members and students who were not officially registered for the workshop. All sessions had a good audience, including the very last one.

The workshop was graced by three excellent invited talks and the quality of the contributed presentations was consistently high. It was very pleasing to see many young researchers deliver clear, well prepared and well paced presentations. You can find all the abstracts for the contributed presentations and the slides for nearly all the talks here.

The invited talks were delivered by Rocco De Nicola (IMT Lucca, IT), Marta Kwiatkowska (University of Oxford, UK) and Jiri Srba; (Aalborg University, DK).

Rocco kicked off the workshop with a talk entitled Languages and Models for Collective Adaptive Systems (slides). Collective Adaptive Systems are heterogeneous collections of autonomous task-oriented systems that cooperate on common goals forming a collective system. Such systems consist of massive numbers of components that interact in complex ways amongst themselves and with other systems; they operate in open and non-deterministic environments, dynamically adapting to new requirements, technologies and environmental conditions. Developing such systems poses challenges to the developers such as the sheer number of components, the need to adapt to changing environments and requirements, the emergent behaviour resulting from complex interactions and the uncertainty both at design-time and at run-time. In his talk, Rocco presented the SCEL language developed by his research group for programming collective adaptive systems and its underlying theory.

Jiri delivered the Thursday invited talk on  Techniques and Tools for thefl Analysis of Timed Workflows (slides). According to Wikipedia, a work flow consists of an orchestrated and repeatable pattern of business activity enabled by the systematic organization of resources into processes that transform materials, provide services, or process information. Many such workflows have strong real-time requirements, and their modelling and analysis is a significant challenge.

In his talk, Jiri suggested a workflow model based on timed-arc Petri nets and introduced the foundational problems of soundness and strong (time-bounded) soundness. He addressed the decidability of these problems and showed, among other results, that soundness is decidable for monotonic workflow nets while reachability is undecidable. For general timed-arc workflow nets, soundness and strong soundness become undecidable, though one can design efficient verification algorithms for the practically interesting subclass of bounded nets. Finally, he demonstrated the usability of the theory by presenting case studies dealing with a Brake System Control Unit used in aircraft certification, the MPEG2 encoding algorithm, a blood transfusion workflow and a home automation system for a family house.

The implementation of the algorithms is freely available as a part of the model checker TAPAAL, which I encourage you to try. 

Last, but not least, Marta delivered  an invited  talk on Computing Reliably with Molecular Walkers (slides). DNA computing is emerging as a versatile technology that promises a vast range of applications, including biosensing, drug delivery and synthetic biology. DNA logic circuits can be achieved in solution using strand displacement reactions, or by decision-making molecular robots, so called 'walkers', that traverse tracks placed on DNA 'origami' tiles. (See, for instance, Luca Cardelli's work.) Similarly to conventional silicon technologies, ensuring fault-free DNA circuit designs is challenging, with the difficulty compounded by the inherent unreliability of the DNA technology and lack of scientific understanding. In her talk, Marta gave an accessible  overview of computational models that capture DNA walker computation and demonstrated the role of quantitative verification and synthesis in ensuring the reliability of such systems. Since stochasticity is an essential component of DNA computing, not surprisingly Marta and her collaborators use the tool PRISM, whose development has been led by Marta herself, in modelling and analysis of molecular programs.

Marta and her co-workers applied quantitative modelling, verification and synthesis to three DNA case studies:

1. DNA tranducer gate design (with Luca Cardelli),
2. DNA walker design (with AndrewTurberfield's lab) and
3. DNA origami dimer (also with AndrewTurberfield's lab).

All were continuous-time Markov chain models, and the first two were modelled analyzed successfully in PRISM. The third proved to be beyond the current capabilities of the tool. If you are interested, you will find papers on those case studies on Marta's publication page.

The workshop also had some local impact. In particular, several members of our association of female students in computer science met with Marta Kwiatkowska, Hanne Riis Nielson and other female participants to discuss about CS in an informal setting and learn from successful female role models, apart from those at their own institution. We thank these female colleagues for their mentoring role.

All in all, it seems to me that NWPT is excellent health and that many workshops, even with published proceedings, can only dream of having the type of support and environment that NWPT boasts.(The NWPT is an informal workshop without published proceedings, but there will be a special issue of a journal to which we will invite some selected contributions.)

The next edition of the workshop will be held in Aalborg. So the workshop will come back to Denmark, where it has not been held since 2009.

October 2015 issue of the Bulletin of the EATCS

The 117th issue of the EATCS Bulletin is now available online at http://bulletin.eatcs.org/index.php/beatcs/issue/view/19.

You can download a pdf with the printed version of the Bulletin from this link. 

As is customary for October issues of the Bulletin, this volume includes reports from ICALP 2015 and calls for nomination for EATCS Awards.

The contributions to the BEATCS columns are all interesting as usual. Let me just limit myself to mentioning that the contribution to the Concurrency Column by Ornela Dardha celebrates the prize she received for the Best Italian Dissertation in TCS in 2014. Fans of the Automata Tutor like me will want to read  the piece written by some of the prime movers behind the development of that wonderful tool.

Readers of this post might also be interested in the article Fast Algorithms for Structured Sparsity by Chinmay Hegde, Piotr Indyk and Ludwig Schmidt, which reports on the work on which the ICALP 2015 tutorial by Piotr was based. 

Thanks to Kazuo Iwama, the editor in chief of the BEATCS, the column editors, the colleagues who contributed to this issue of the Bulletin and Efi Chita from the EATCS Secretary Office for their wonderful work.

I hope that you'll enjoy this issue. I think that it is the duty of a scientific association like the EATCS to make its bulletin freely available to the TCS community. However, this would be impossible without the support from the members of the EATCS, whom I thank wholeheartedly.

CFP: 15th Scandinavian Symposium and Workshops on Algorithm Theory

This event is taking place at Reykjavik University in June 2016. Consider submitting!

==========================================

SWAT 2016 - Call for Papers

15th Scandinavian Symposium and Workshops on Algorithm Theory
June 22-24, 2016, Reykjavik, Iceland

==========================================
Submission deadline: Feb 14, 2016
http://www.ru.is/~mmh/swat16/index.html
==========================================

SCOPE

The symposium, which alternates with the Algorithms and Data Structures
Symposium (WADS), is a forum for researchers in the area of design and
analysis of algorithms and data structures. We invite submissions of
papers presenting original research on algorithms and data structures.
Though we welcome experiments, the theoretical results in the articles
will be the main measure for evaluating their merits. Algorithmic
approaches of interest include, but are not limited to: approximation
algorithms, parametrized algorithms, distributed algorithms, parallel
algorithms, external-memory algorithms, data structures, exponential
time algorithms, online algorithms, randomized algorithms, streaming
algorithms, sub-linear algorithms. The algorithmic problems considered
may be motivated by applications, e.g. in optimization, geometry and
topology, graph analysis, bioinformatics, visualization, string
processing, information retrieval, machine learning, algorithmic game
theory, or mechanism design.


SUBMISSIONS

Contributors must submit their papers using the Easychair system.
Submissions should be in LIPIcs format (without font size, margin, or
line spacing changes), and not exceed 12 pages including front page and
references. See
www.dagstuhl.de/publikationen/lipics/anleitung-fuer-autoren/
for instructions. Additionally, if full details of proofs do not fit
into the page limit, a clearly marked appendix containing the remaining
details must be included; this appendix will not be regarded as part of
the submission and will be considered only at the discretion of the
program committee. Submissions deviating substantially from this format
risk rejection without consideration of their merits.

Papers submitted for review should represent original, previously
unpublished work. At the time the paper is submitted to the symposium,
and for the entire review period, the paper (or essentially the same
paper) must not be under review by any other conference with published
proceedings or by a scientific journal. However, we encourage authors to
make a preprint of their paper available at a public repository such as
arXiv. At least one author of every accepted paper is expected to register
and present the paper at the symposium. Symposium proceedings will be
published in the "Leibniz International Proceedings in Informatics"
(LIPIcs) series.


IMPORTANT DATES

Submission deadline: Feb 14, 2016
Author notification: Early April, 2016
Symposium: Feb 17-20, 2016


BEST STUDENT PAPER

A prize will be awarded to the author(s) of the best student-authored
paper. A paper is eligible if all of its authors are full-time students
at the time of submission. This must be indicated in the submission
process.


PROGRAM COMMITTEE

 - Christian Sohler, Technische Universität Dortmund
 - Christian Wulff-Nilsen, University of Copenhagen
 - Dimitris Fotakis, National Technical University of Athens
 - Djamal Belazzougui, University of Helsinki
 - Ely Porat, Bar-Ilan University
 - Fabio Vandin, University of Padova
 - Faith Ellen, University of Toronto
 - Francois Le Gall, University of Tokyo
 - Gerhard Woeginger, Eindhoven University of Technology
 - Gonzalo Navarro, University of Chile
 - Kasper Green Larsen, Aarhus University
 - Marek Karpinski, University of Bonn
 - Marina Papatriantafilou, Chalmers University of Technology and Göteborg University
 - Nodari Sitchinava, University of Hawaii, Manoa
 - Ola Svensson, École Polytechnique Fédérale de Lausanne
 - Petteri Kaski, Aalto University
 - Pinar Heggernes, University of Bergen
 - Rasmus Pagh (chair), IT University of Copenhagen
 - Rob van Stee, University of Leicester
 - Seth Pettie, University of Michigan
 - Stefan Langerman, Université libre de Bruxelles
 - Suresh Venkatasubramanian, University of Utah
 - Therese Biedl, University of Waterloo


ORGANIZING COMMITTEE

 - Christian Konrad, Reykjavík University
 - Magnús M. Halldórsson, Reykjavík University (chair)
 - Páll Melsted, University of Iceland
 - Tigran Tonoyan, Reykjavík University


STEERING COMMITTEE

 - Andrzej Lingas, Lund University
 - Esko Ukkonen, University of Helsinki
 - Jan Arne Telle, University of Bergen
 - Lars Arge, Aarhus University
 - Magnús M. Halldórsson, Reykjavík University


CONTACT INFORMATION

 -http://www.ru.is/~mmh/swat16/  (general information)

The EATCS Distinguished Dissertation Awards 2015: Call for Nominations

The EATCS has established the Distinguished Dissertation Award to promote and recognize outstanding dissertations in the field of Theoretical Computer Science. Any PhD dissertation in the fi eld of Theoretical Computer Science that has been successfully defended in 2015 is eligible.

Three dissertations will be selected by the committee for year 2015. The dissertations will be evaluated on the basis of originality and potential impact on their respective fields and on Theoretical Computer Science.

Each of the selected dissertations will receive a prize of 1000 Euro. The award receiving dissertations will be published on the EATCS web site, where all the EATCS Distinguished Dissertations will be collected.

The dissertation must be submitted by the author as an attachment to an email message sent to the address giuper@gmail.com by December 31st, 2015 with subject EATCS Distinguished Dissertation Award 2015. The body of the message must specify:

• Name and email address of the candidate;
• Title of the dissertation;
• Department that has awarded the PhD and denomination of the PhD program;
• Name and email address of the thesis supervisor;
• Date of the successful defence of the thesis.

A five page abstract of the dissertation and a letter by the thesis supervisor certifying that the thesis has been successfully defended must also be included. In addition, the author must include an endorsement letter from the thesis supervisor and can include one more endorsement letters.

The dissertations will be selected by the following committee:

• Javier Esparza (Munich, Germany)
• Michal Feldman (Tel Aviv, Israel)
• Fedor Fomin (Bergen, Norway)
• Luke Ong (Oxford, United Kingdom)
• Giuseppe Persiano (Salerno, Italy)

The award committee will solicit the opinion of members of the research community as appropriate.

Theses supervised by members of the selection committee are not eligible.

The EATCS is committed to equal opportunities, and welcomes submissions of outstanding theses from all authors.

Running a research centre in TCS in Iceland for ten years

ICE-TCS, our small research centre in theoretical computer science at Reykjavik University, is ten years old. Magnús M. Halldórsson, Anna Ingólfsdóttir and I, together with some other kindred spirits, decided to found the centre in the spring of 2005 to exploit the available scientific strengths, whatever those might be, in theoretical computer science  and discrete mathematics in order to

• focus the research efforts, and establish synergies amongst the active researchers in Iceland,
• attract outstanding researchers in Theoretical Computer Science to Iceland for short- or long-term visits leading to collaborations with local researchers and to improvements in the Icelandic research environment,
• organize international conferences and workshops in Theoretical Computer
  Science in Iceland to put the country firmly on the map as a recognized
  conference location for high quality events in the field, and
• attract young, outstanding students from Iceland to this research area.

The research centre was started as a collaboration between the Department of
Computer Science, Faculty of Engineering, University of Iceland, and the School of Computer Science, Reykjavik University. However, all the activities of the centre have taken place at Reykjavik University since Magnús, who has been the director of ICE-TCS since its inception, took up a professorship at the School of Computer Science at Reykjavik University in August 2007.

The inspiration for starting the centre derived from the experience that Anna and I had with BRICS (the Basic Research in Computer Science centre of the Danish National Research Foundation), which ran, with generous funding, in Aarhus and Aalborg from 1994 till 2006. 

It is not up to me to say whether we have achieved any of the above-mentioned objectives over the last ten years. I encourage our scientific advisory board and you to have a look at the ICE-TCS web site to get an idea of the main events that we have organized over the last decade and to form your own opinions. Here I will simply limit myself to saying that I do believe that starting the centre was necessary at that time and that without ICE-TCS the academic environment in computer science in Iceland would have been much less attractive and interesting  for those amongst us who try to carry out research in TCS and discrete mathematics. The Icelandic research community in (T)CS is simply too small to consist of islands of isolated individuals. IMHO, one needs centre-like structures to sustain a community that is capable of organizing events such as a weekly seminar series that one takes for granted in larger CS departments.

A former colleague from Aalborg University used to say that "lone rangers die".  The brightest and most motivated researchers amongst us would be able to keep producing top-class work even alone on Mars, but I do believe that, for the common mortals amongst us, the existence of a research ecosystem, no matter how small, does help us stay "alive", in the sense of  Paul Erdős, a little longer.  I hope that my colleagues at ICE-TCS over the years feel that the centre has played a positive role in their careers and  in their daily work.

Despite our chronic lack of centre-specific funding, we have made the most of the lure of Iceland and have succeeded in attracting guests to ICE-TCS. To do so, we have had to use every available source of ad hoc funding, not to mention the fact that many of our guests often paid for their own travel and accommodation. (This is where being located in a hip place like Iceland does help.) On behalf of ICE-TCS, I thank all the colleagues who have graced our centre with their visits, which have often led to joint papers and long-term collaborations.

I like to think that we have done our share for the TCS by hosting the best attended ICALP ever in 2008, DisCoTec 2011, 6th International Federated Conferences on Distributed Computing Techniques, and the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2012) amongst other events. If you are interested in visiting us, combining business and pleasure, you might consider submitting to the  15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) or to LICS 2017. In addition, we have organized an annual theory day since 2005, with the goal of preaching the gospel of TCS to the local CS community and to our students. We have taken part in the Alan Turing Year and we followed it up with a seminar series on Pearls of Computation, which, despite our best intentions, is not attracting as many participants as we had hoped.

In summary, these have been ten very exciting years and we do not plan to close the centre yet. Starting the centre is a decision I personally do not regret, despite the work needed to keep it ticking. Whether my colleagues and I will have the energy and the drive to keep going for a few years more is something I do not know. I just hope that some of our young and enthusiastic members will step up to the challenge of making the centre thrive in its second decade of existence. Time will tell whether ICE-TCS will become a teenager.

Call for Nominations: EATCS FELLOWS 2016

CALL FOR NOMINATIONS FOR EATCS FELLOWS 2016

• VERY IMPORTANT: all nominees and nominators must be EATCS Members
• Proposals for Fellow consideration in 2016 should be submitted by DECEMBER 31st, 2015 by email to the EATCS Secretary (secretary@eatcs.org). The subject line of the email should read "EATCS Fellow Nomination - surname of candidate".

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, chair) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France)
- 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 2016 must be received by December 31, 2015.

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)