EATCS Award 2016 to Dexter Kozen (Cornell University, USA)

The EATCS bestows the EATCS Award 2016 to Dexter Kozen (Cornell University, USA) for fundamental contributions across the whole spectrum of theoretical computer science

The EATCS is proud to announce that the EATCS Award Committee consisting of Fedor Fomin, Kim G. Larsen (chair) and Jean-Eric Pin has selected Dexter Kozen (Cornell University, USA; http://www.cs.cornell.edu/~kozen/)  as the recipient of the EATCS Award 2016.

Dexter Kozen is a theoretical computer scientist, perhaps the  theoretical computer scientist, who has excelled across the entire spectrum of our field and crashed through the so-called Volume A/Volume B barrier. Even within these tracks he has exhibited remarkable diversity and depth. This makes him an exceptional candidate for the EATCS Award and he continues the lineage of stellar scientists who have received the EATCS Career Award so far.

Dexter Kozen is known for his many contributions to theoretical computer science. These include, among many others, the most succinct and beautiful proof imaginable of completeness for PDL, a stunning treatment of the far more challenging mu-calculus and the elegant treatment of logics of programs in the setting of Kleene algebra. He has also made fundamental contributions to complexity theory. In fact, one of the first contributions of Dexter Kozen to the scientific community was the definition of the notion of alternating Turing machine, a deep contribution to complexity theory that made it possible to connect time and space complexity. The results were viewed as so significant that they almost immediately became part of the graduate curriculum in complexity theory. Dexter’s work on alternation appeared initially in his singly-authored FOCS’76 paper, independent of the Chandra-Stockmeyer paper that was published back-to-back with it in the same volume; the two later became the famous combined, very high-cited, triply-authored J.ACM version for which the authors won an IBM Outstanding Innovation Award in 1980.

Dexter Kozen’s work on modal logic and Kleene algebra has undoubtedly had a major impact in the area of programming logics and gathered a huge number of citations as it opened up this field.

Besides complexity theory and modal logic, Dexter Kozen also produced major results on algebra, such as the complexity of the theory of real closed algebraic theories, and on computer algebra, such as the Kozen-Landau theorem.

Dexter Kozen has also been a pioneer in probabilistic semantics. Long before it became fashionable, he worked on a measure-theoretic semantics  for probabilistic programs which remains the inspiration for the intense activity in topics like probabilistic programming languages, probabilistic process algebra and logics.

Dexter Kozen has had many collaborations. His connections to Amsterdam, Aarhus and Warsaw are probably the most well-known. He has spent several one year sabbaticals in Europe with successful collaborations. He is an inspiring person  and his presence in a department is of immeasurable value for young researchers. It is worth mentioning that Dexter Kozen’s support for the contacts with Eastern European colleagues has been admirable, at a time when this was rather difficult and complex to achieve.

David Harel's two-page  laudation that appears in the volume for Dexter's 60th birthday (available at http://www.wisdom.weizmann.ac.il/~harel/papers/Kozen.pdf) provides a wonderful introduction to Dexter Kozen as a scientist and as a colleague.

The  EATCS Award is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life-long scientific career. The list of the previous recipients of the EATCS Award is available at

http://eatcs.org/index.php/eatcs-award.

The EATCS Award carries a prize money of 1000 Euros and will be presented at ICALP 2016, which will take place in Rome (Italy) from the 12th till the 15th of July 2016.

Report on Dagstuhl Seminar 15511 on the Graph Isomorphism Problem (contribution by Anuj Dawar)

Anuj Dawar has kindly allowed me to post here his report on Dagstuhl Seminar 15511 on the Graph Isomorphism Problem, which will appear in the February 2016 issue of the Bulletin of the EATCS. IMHO, it is a real gem and conveys the excitement of the event wonderfully well. Enjoy it!

The February 2016 issue of the BEATCS will be brimming with interesting and though-provoking content, and will be open access as usual. I hope that you'll make a point of reading it, when it is published. Watch this space for further news on the issue.

Computer Science in Europe (contribution by Thomas A. Henzinger)

This is the second viewpoint piece I received in response to my call for opinions on the report on logic activities in Europe that Yuri Gurevich wrote in 1992. Thanks to Tom for taking the time to write this piece and for allowing me to share it on this blog. Enjoy it! 

Computer Science in Europe

Thomas A. Henzinger

IST Austria 

It saddens me but it would be difficult to refute a claim that, in the past two decades, Europe has been falling further behind the United States in the dynamism of the information technology industry, the popularity of the computer science major, and the impact of frontier research in computing. The vast majority of Turing awards still goes to researchers who work in the United States. It is particularly disconcerting that the main strengths of European computer science appear largely unchanged from 1994: on the academic side, Europe's research leaders are still concentrated disproportionately in formal methods, and on the industrial side, Europe's technology leaders are still found primarily in the "old" economy, exemplified by the automotive industry.

To close the gap, Europe desperately needs new organizational structures in academia, a greater entrepreneurial spirit of society, an improved image for computer science as a career choice, especially among women, the mandatory acquisition of computational thinking and coding skills in secondary education, and more emphasis on principles of systems building which are critical to industry in university curricula of computer science. Israel offers a role model for closing the gap with the United States with regard to the first three points ---academic structures, entrepreneurial culture, and the public image of computer science--- and has been a leader in computer science education.

There are a few encouraging signs of European computer science changing. The European systems community has begun to organize itself through efforts such as the Eurosys conference and some countries are trying to remedy their deficiencies in systems research. Germany, for example, founded the Max Planck Institute for SoftwareSystems. Several European countries and institutions have started to copy key aspects of the American career model, such as tenure tracks that give faculty early independence and doctoral programs that give students a broad graduate education. Student mobility and structured doctoral education are strongly supported by the Marie Curie program of the European Union and by the funding agencies of some countries, to counteract the wide-spread habit of researchers advancing in the same lab from undergraduate to faculty level.

There have been some remarkable institutional changes. EPFL has demonstrated that changes in the organization and recruiting can lead to dramatic improvements in the scientific reputation and attractiveness of an institution. Even entirely new institutions have been founded, such as IST Austria, which naturally find it easier to implement new structures such as a tenure track and an institutional doctoral school.

The most significant development can be found, perhaps surprisingly, on the European level. I am referring to the creation of the EuropeanResearch Council, which supports frontier research based purely on scientific criteria. This program has no counterpart in the United States, but if it manages to remain scientifically independent and well-funded, I am confident that its impact will change the game. These are big if's, of course, and the ERC is constantly being threatened by national interests and sectorial lobbies that favor traditional programs which distribute the available funds to more different countries, sectors, and groups. Given that politicians love to pride themselves with the founding of "strategic" consortia, centers, and flagships, and industry likes to get every possible cut of public money, the initial success of the ERC has been all the more remarkable. Let's work together so that it will trump the less effective funding formats and lift the strength of computer science in Europe.

On the Two Sides of the Atlantic in Logic and Computation (contribution by Moshe Y. Vardi)

Prompted by a reference to it in a recent CACM editorial by Moshe Vardi, I belatedly read the very interesting piece on logic activities in Europe that Yuri Gurevich wrote in 1992. I was struck by the idea that it might be interesting to ask some selected colleagues to contribute (short) opinion pieces to the Bulletin of the EATCS reflecting on the points raised by Yuri in that article twenty years later. 
In order to whet your appetite, I post below Moshe's contribution. Thanks to Moshe for taking the time to write this piece and for allowing me to share it on this blog. Enjoy it! 

On the Two Sides of the Atlantic in Logic and Computation

MosheY. Vardi

Rice University

In his 1977 EWD Note 611, “On the fact that the Atlantic Ocean has twosides,” Edsger Dijkstra noted the different attitudes towards computing research in Northern America and Western Europe. Yuri Gurevich noted the same phenomenon in his 1992 report, "Logic Activities inEurope." In a 2015 Communications of the ACM editorial I revisited this issue and asked “Why Doesn't ACM Have a SIG for Theoretical ComputerScience?^"

The key issue raised in that editorial was the split between Volume-A-type and Volume-B-type research in Theoretical Computer Science (TCS), referring to the 1990 Handbook of Theoretical Computer Science, with Jan van Leeuwen as editor. The handbook consisted of Volume A, focusing on algorithms and complexity, and Volume B, focusing on formal models and semantics. In other words, Volume A is the theory of algorithms, while Volume B is the theory of systems (hardware and software). North American TCS tends to be quite heavily focused on Volume A, while European TCS tends to encompass both Volume A and Volume B. The ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) is, de facto, a special-interest group for Volume-A TCS.

I pointed out in my editorial that this division did not exist prior to the 1980s. In fact, the tables of contents of the proceedings of two North American premier TCS conferences—IEEE Symposium on Foundations of Computer Science (FOCS) and ACM Symposium on Theory of Computing (STOC)---from the 1970s reveal a surprisingly (from today's perspective) high level of Volume-B content. In the 1980s, the level of TCS activities in North America grew beyond the capacity of two annual single-track three-day conferences, which led to the launching of what was known then as "satellite conferences." Shedding the "satellite" topics allowed FOCS and STOC to specialize and develop a narrower focus on TCS. But this narrower focus in turn has influenced what is considered TCS in North America. In contrast, the European Association for Theoretical Computer Science (EATCS), expanded the scope of its flagship conference, the International Colloquium on Automata, Languages, and Programming (ICALP), by reorganizing the conference along several tracks. In 2015, ICALP consisted of three tracks: Track A: Algorithms, Complexity and Games; Track B: Logic, Semantics, Automata and Theory of Programming; and Track C: Foundations of Networked Computation: Models, Algorithms and Information Management. The reorganization along tracks allowed EATCS to broaden its scope, rather than narrow it like SIGACT.

But the reality is that if one zooms into Volume-B research, one finds again the Volume-A/Volume-B dichotomy, also reflected in the range of topics of the Symposium on Logic in Computer Science (LICS), the flagship conference of the ACM Special Interest Group on Logic and Computation (SIGLOG). Sub-volume A of Volume-B research is concerned with connections between logic, algorithms, and computational complexity. Descriptive-Complexity Theory, for example, aims at bridging computational complexity and logic by studying the expressive power needed to describe problems in given complexity classes. A celebrated result in this area is Fagin’s Theorem, which relates NP to Existential Second-Order Logic. Model Checking, as another example, studies the evaluation of logical formalisms, including various temporal logics, over finitely represented structures. Automata theory often provides tools to bridge between logic and algorithms. The Büchi-Elgot-Trakhtenbrot Theorem, for example, provides automata-theoretic tools for solving the satisfiability problem for Monadic Second-Order Logic on finite words.

Sub-volume B of Volume-B research, in contrast, is concerned with semantical and methodological foundations for programming and programming languages. Domain theory, for example, studies special kinds of partially ordered sets called domains. Domain theory is used to specify denotational semantics, especially for functional programming languages. Category theory, as another example, formalizes mathematical structure and its concepts in terms of a collection of objects and of arrows (also called morphisms). Category theory provides powerful modeling idioms and has deep connections to types in programming languages. Concurrency theory studies formalisms for modeling and analyzing concurrent systems. Proof Theory is of major interest in Sub-volume B of Volume B research, and a distinguished result is the Curry–Howard Correspondence, which provides a direct relationship between types in computer programs and formal proofs in certain logics.

The split between Sub-volumes A and B within Volume-B research can perhaps be traced to the standard division of mathematical Logic into several branches: computability theory, model theory, proof Theory, and set Theory. (See the 1989 Handbook of Mathematical Logic, with John Barwise as editor.) While set theory has no clear computer-science counterpart, Sub-volume A of Volume-B research can be traced to computability theory and model theory, while Sub-volume B of Volume-B research can be traced to proof theory. Indeed, a scientific discipline, as it grows and matures, inevitably grows branches, which gradually grow apart from each other. As scientists are forced to go deeper, it becomes gradually impossible for them to keep track of developments in more than a very small number of branches. In fact different branches develop their own specialized languages, impeding communication between branches.

It is often at the interfaces between branches, however, that the most exciting developments occur. Consider Artificial Intelligence, for example. Since the establishment of the field in the late 1950s, logic has played a key role as the fundamental formalism for describing reasoning. Ultimately, however, logical tools were not fully adequate to capture the common-sense reasoning that characterizes human reasoning. In the 21^st Century, probabilistic and statistical approaches have become dominant, for example, in machine learning. Synthesizing the logical and probabilistic approaches is a new frontier, where I expect to see many exciting developments in the next few years.

Finally, while 25 years ago computing-research took place mostly in North America and Western Europe, computing research has since globalized. The Atlantic Ocean is no longer as dominant as it used to be. I look forward to the day when we will write about “The Two Sides of the Pacific/Indian Ocean in Logic and Computation.”

EC comes to Europe

The EC'16 conference will be held in lovely Maastricht, NL next year with Vincent Conitzer as general chair. As far as I can tell, this is the second time that EC comes to Europe in its 17-year history. This is a step that, as president of the EATCS, I warmly welcome.

Submit your best work to EC'16 and you'll have a chance to visit a historical city at the heart of Europe to boot!

Four EATCS Awards with deadline for nominations on the 31st of December 2015

This is to remind you that the deadline for nominations for the following awards is the 31st of December 2015:

    EATCS Award: http://eatcs.org/index.php/eatcs-award
    EATCS Distinguished Dissertation Award: http://www.eatcs.org/index.php/dissertation-award
    EATCS Fellows: http://www.eatcs.org/index.php/eatcs-fellows
    Presburger Award: http://eatcs.org/index.php/presburger

I strongly encourage members of the TCS community to nominate eligible colleagues for these accolades. Writing a good letter of nominations takes a little work, but  this is time well spent as it puts some of the many outstanding members of our community and their research areas in the spotlight, and provides role models for the younger members of the TCS community.

Call for nominations for the 2016 Alonzo Church Award

It's been a long journey, but the Alonzo Church Award is finally off the ground. Here is the call for nominations I just received from the first award committee. You will notice that the deadline for nominating papers for the first award is close: March 1, 2016.  (Of course, the call for nominations will be issued earlier next year.) For the time being, I hope that you will follow Littlewood's zero-infinity law: If you  have a paper (or papers) you'd like to nominate for the award, do it now, where in this case "now" means "by the end of February 2016" :-)

The award committee, whose members I thank on behalf of the EATCS, look forward to receiving your nominations!

The 2016 Alonzo Church Award

for

Outstanding Contributions to Logic and Computation

Call for Nominations

Introduction

An annual award, called the Alonzo Church Award for Outstanding Contributions to Logic and Computation, was established in 2015 by the ACM Special Interest Group for Logic and Computation (SIGLOG), the European Association for Theoretical Computer Science (EATCS), the European Association for Computer Science Logic (EACSL), and the Kurt Gödel Society (KGS). The award is for an outstanding contribution represented by a paper or by a small group of papers published within the past 25 years. This time span allows the lasting impact and depth of the contribution to have been established. The award can be given to an individual, or to a group of individuals who have collaborated on the research. For the rules governing this award, see

http://siglog.hosting.acm.org/the-alonzo-church-award-for-outstanding-contributions-to-logic-and-computation/

Eligibility and Nominations

The contribution must have appeared in a paper or papers published within the past 25 years. Thus, for the 2016 award, the cut-off date is January 1, 1991. When a paper has appeared in a conference and then in a journal, the date of the journal publication will determine the cut-off date. In addition, the contribution must not yet have received recognition via a major award, such as the Turing Award, the Kanellakis Award, or the Gödel Prize. (The nominee(s) may have received such awards for other contributions.) While the contribution can consist of conference or journal papers, journal papers will be given a preference.

Nominations for the 2016 award are now being solicited. The nominating letter must summarize the contribution and make the case that it is fundamental and outstanding. The nominating letter can have multiple co-signers. Self-nominations are excluded. Nominations must include: a proposed citation (up to 25 words); a succinct (100-250 words) description of the contribution; and a detailed statement (not exceeding four pages) to justify the nomination. Nominations may also be accompanied by supporting letters and other evidence of worthiness.

Nominations are due by March 1, 2016, and should be submitted to vardi@cs.rice.edu.

Presentation of the Award

The 2016 award will be presented at LICS, the flagship conference of SIGLOG. The award will be accompanied by an invited lecture by the award winner, or by one of the award winners. The awardee(s) will receive a certificate and a cash prize of USD 2,000. If there are multiple awardees, this amount will be shared.

Award Committee

The 2016 Alonzo Church Award Committee consists of the following four members: Catuscia Palamidessi, Gordon Plotkin, Wolfgang Thomas, and Moshe Vardi (chair).

The 'novelty' of arXiv overlay journals

Last September, Nature published an article on a new publishing initiative by Timothy Gowers. The Nature piece starts thus:

"New journals spring up with overwhelming, almost tiresome, frequency these days. But Discrete Analysis is different. This journal is online only — but it will contain no papers. Rather, it will provide links to mathematics papers hosted on the preprint server arXiv. Researchers will submit their papers directly from arXiv to the journal, which will evaluate them by conventional peer review."

and ends as follows:

"The question, perhaps, is how readily researchers will embrace the model. “Apart from being an arXiv overlay journal, our journal is very conventional, which I think is important so that mathematicians won't feel it is too risky to publish in it,” says Gowers. “But if the model becomes widespread, then I personally would very much like to see more-radical ideas tried out as well” — for example, post-publication review and non-anonymous referees."

Based on the first paragraph of this blog post by Timothy Gowers, it is highly likely that Discrete Analysis will start by publishing some very strong papers. This will probably play an important role in enticing mathematicians to publish some of their best work in it and in giving the new journal a good impact factor within a reasonable amount of time.

However, as mentioned in the Nature piece and as Gowers himself pointed out in his blog post announcing Discrete Analysis, arXiv overlay journals are not new. In TCS, Logical Methods in Computer Science published its first issue ten years ago and has become one of the favourite publication outlets for researchers working on logic in computer science, broadly construed. Logical Methods in Computer Science is an open-access journal, covered by Thompson ISI , SCOPUS, DBLP, Mathematical Reviews and Zentralblatt. (Impact factor: 0.443.) All journal content is licensed under a Creative Commons license.

Moreover, the 'arXiv overlay principle' is also used by Electronic Proceedings in Theoretical Computer Science (EPTCS), an international refereed open access venue for the rapid electronic publication of the proceedings of workshops and conferences, and of Festschriften, etc, in the general area of theoretical computer science, broadly construed. This proceedings series, which was initiated in 2008-2009 by the sterling effort of Rob van Glabbeek, has published 200 volumes at the time of writing this blog post. (Congrats to EPTCS for reaching the milestone of 200 volumes!)

Just like Discrete Analysis will do, Logical Methods in Computer Science (and EPTCS for workshops and conferences) only publishes papers that have undergone classic peer review and have been vetted for publication by the cognizant editor. For what it is worth, I therefore fail to see why Logical Methods in Computer Science and Discrete Analysis, once it starts publishing papers, are not doing journal publishing, as hinted in this excerpt from a post from the scholarly kitchen:

"My view is that while this is a fascinating way to draw out from arXiv links to good preprints in relevant fields, this is not journal publishing. In Gower’s blog he moves on from talking about the idea of the overlay journal to a more polemical discussion of how his venture is in essence the future of the journal, reducing costs and supplying quality content in a way that may be used in the same way journal articles are used now. While Gowers has every right to his views on this, I would argue that, while his is certainly an exciting way to make use of preprints in arXiv, what it does is quite distinct from a journal. As discussed above, the journal is a matter of record, and like it or not, journals form a part of the academic and recognition workflow that allows for career progress, grant making, more research and more articles to be published."

Logical Methods in Computer Science is "a matter of record", and publishing in it does carry weight in hiring and promotion decisions. Prime conferences in the field, such as LICS, have used it for their special issues.

Whether a journal publishes its contents as overlay of the arXiv or by some other means, IMHO it is the process that went into selecting the papers and the scientific quality of what is published that matter.

EATCS Awards 2016: Deadline approaching!

This is to remind you that the deadline for nominations for the following EATCS awards is the 31st of December 2015:

EATCS Award: http://eatcs.org/index.php/eatcs-award
EATCS Distinguished Dissertation Award: http://www.eatcs.org/index.php/dissertation-award
EATCS Fellows: http://www.eatcs.org/index.php/eatcs-fellows
Presburger Award: http://eatcs.org/index.php/presburger

I strongly encourage members of the TCS community to nominate eligible colleagues for these accolades. Writing a good letter of nominations takes a little work, but this is time well spent as it puts some of the many outstanding members of our community and their research areas in the spotlight, and provides role models for the younger members of the TCS community.

The deadline for nominations for the Gödel Prize (http://eatcs.org/index.php/goedel-prize) is January 31, 2016.

The award committees for the above-mentioned prizes and honours look forward to receiving your nominations!

Logarithms in the cultural pages of an Italian newspaper

Last Saturday, the cultural pages of a major Italian newspaper featured an article with the title "Arte digitale - la creatività salvata da social e logaritmi" ("Digital art - creativity saved by social networks and logarithms", sic) . The article ends with the following war cry: un "logaritmo vi seppellirà" oppure un "logaritmo vi salverà! " (a logarithm will bury you or a logarithm will save you!).

Well, after all, "logarithm" is an anagram of "algorithm" :-)

Whence Algorithmic Game Theory?

I recently saw the slides for the invited talk delivered by Moshe Vardi at SR 2015, the third International Workshop on Strategic Reasoning, which was held in Oxford in the period 21-22 September 2015. The talk was entitled A Revisionist History of Algorithmic Game Theory and must have stimulated some discussion at the workshop.

Moshe's message was that algorithmic game theory is older than the "official history" would make one believe and that

• it was initiated by logicians in 1957,
• it was revitalized by Vol. B TCS in 1989 , and 
• has been active in Volume B TCS since then. 

The most important message, however, is that one should tear down the wall between Vol. A and Vol. B. As readers of this blog may have realized, this is a message to which I wholeheartedly subscribe, perhaps because in the small research community I live in, we have to go to each other's talks to even have an audience at all.

Call for Workshops Proposals affiliated with ICALP 2016

Irene Finocchi asked me to distribute the appended call for workshop proposals for ICALP 2016. If you plan to organize a TCS workshop, why not co-locating it with that conference in Rome? The workshop chair is Nicola Galesi.

Call for Workshops Proposals affiliated with ICALP 2016
July 11-15, 2016,  Rome, Italy

Workshop proposals are solicited for ICALP 2016. A workshop may relate to any of the three tracks of ICALP, but proposals related to all aspects of theoretical computer science will be considered as well.

ICALP workshops typically feature a number of invited speakers and a number of contributed presentations.  Workshops will be held on the first day of the conference (July 11, 2016) and will have a duration of at most one day.

Workshop proposals should be no longer than two pages and should include:
- title of the workshop;
- person(s) responsible for the workshop (name and email address);
- a short scientific summary and justification of the proposed topic. This should include a discussion of the particular benefits of the topic to the ICALP community;
- the proposed format and agenda;
- procedures for selecting participants and papers;
- expected number of participants.

Proposals should be sent in pdf format to icalp2016@di.uniroma1.it

Important dates
Submission due: December 20, 2015
Notifications: January 10, 2016
Final program due: 15 May 15, 2016

Further information

We provide the following aspects of the workshop organisation:
- registration;
- wireless network, conference rooms, etc. (as for ICALP);
- a link to the web page of the workshop;
- local support and organization.

We do not provide:
- management of any scientific aspects of the workshop program (the workshop organizers are responsible for call for papers, call for participation, notification, program, workshop webpage, publication of workshop proceedings or journal special issues, etc.);
- publicity for the workshop.

PC chairs for ICALP 2017

I am happy to inform you that the PC chairs for ICALP 2017, which will be held in Warsaw, Poland, in the period 10-14 July 2017 will be:

• Track A: Piotr Indyk (MIT, USA)
• Track B: Anca Muscholl (LaBRI and Université Bordeaux, France)
• Track C: Fabian Kuhn (University of Freiburg, Germany)

The conference chairs will be Mikolaj Bojanczyk and Piotr Sankowski.

On behalf of the EATCS, I thank these colleagues for their willingness to serve.

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)

Call for Nominations: Presburger Award for Young Scientists 2016

Presburger Award for Young Scientists 2016

   Call for Nominations

   Deadline: December 31st, 2015

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 2016 the date of birth should be in 1980 or later). The Presburger Award Committee of 2016 consists of Zoltan Esik (Szeged), Marta Kwiatkowska (Oxford) and Claire Mathieu (Paris, chair).

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:

   Claire Mathieu
   clairemmathieu@gmail.com

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

The award includes an amount of 1000 Euro and an invitation to ICALP 2016 for a lecture.

Previous Winners:

   Mikołaj Bojanczyk, 2010
   Patricia Bouyer-Decitre, 2011
   Venkatesan Guruswami and Mihai Patrascu, 2012
   Erik Demaine, 2013
   David Woodruff, 2014

   Xi Chen, 2015

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