February 2016 issue of the Bulletin of the EATCS

I am happy to inform you that the 118th issue of the EATCS Bulletin is now available online at http://bulletin.eatcs.org/index.php/beatcs/issue/view/20, featuring, amongst others:

- "Computational Aspects of Packing Problems", by Helmut Alt
- "Catalytic computation", by Michal Koucký
- "Fault-Tolerant Logical Network Structures", by Merav Parter
- "Bringing Informatics Concepts to Children Through Solving Short Tasks", by Valentina Dagiene
- "Viewpoints on “Logic activities in Europe”, twenty years later", by Luca Aceto, Thomas A. Henzinger, Joost-Pieter Katoen, Wolfgang Thomas, Moshe Y. Vardi.

You can download a pdf with the printed version of the bulletin from http://www.eatcs.org/images/bulletin/beatcs118.pdf

 

Many thanks to the column editors, the authors of the contributions, Kazuo Iwama, the editor in chief of the BEATCS, and Efi Chita at the EATCS Secretary Office for the enormous work they have put into producing this issue of the Bulletin. 

As usual, thanks to the support of the EATCS members, the Bulletin is freely accessible to everyone. Enjoy it!

EATCS Fellows class of 2016 named

The EATCS has recognized five of its members for their outstanding contributions to theoretical computer science by naming them as recipients of an EATCS fellowship. The EATCS Fellows for 2016 are:

• Zoltán Ésik (University of Szeged, Hungary; http://www.inf.u-szeged.hu/~ze/) for "contributions to the fields of automata and formal languages, iteration theories, algebra and logic in computer science, and in particular to their connections. He has been able to apply deep theorems of some area to problems of other fields, yielding particularly short, beautiful and mathematically concise proofs."
• David Harel (Weizmann Institute of Science, Israel; http://www.wisdom.weizmann.ac.il/~harel/) for "fundamental contributions to program verification, database theory, and software engineering, as well as for exceptional merits as a writer and teacher. The Statecharts model has had profound impact on software and systems engineering."
• Giuseppe F. Italiano (University of Rome Tor Vergata, Italy; http://www.disp.uniroma2.it/users/italiano/) for "fundamental contributions to the design and analysis of algorithms for solving theoretical and applied problems in graphs and massive data sets, and for his role in establishing the field of algorithm engineering."
• Kurt Mehlhorn (Max-Planck-Institut für Informatik, Germany; https://people.mpi-inf.mpg.de/~mehlhorn/) for "his influential contribution to the whole field of algorithmics over the past decades. In addition to key theoretical contributions, he has brought basic research closer to practice."
  
• Scott A. Smolka (Stony Brook University, USA; http://www3.cs.stonybrook.edu/~sas/) for "fundamental contributions to process algebra, model checking, probabilistic processes, runtime verification, and more recently for the successful application of most of these theories to cardiac-cell modelling and analysis."
  

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 2016 consisted of

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

The EATCS Fellows Program was established by the association  in 2014 to recognize outstanding EATCS 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 association among its fellows.

The list of EATCS Fellows is available at  http://www.eatcs.org/index.php/eatcs-fellows.

"Save Italian Research": A petition started by Giorgio Parisi

Giorgio Parisi, an eminent Italian physicist, has started a petition to put pressure on the Italian government to support Italian research adequately. Together with 68 colleagues, he has also written a letter published in Nature, which I copy-paste below from the site of the petition.

Readers of this blog might consider signing the petition.

Addendum: In a comment on this post, Giorgio Parisi invites everyone to sign the petition at https://www.change.org/p/salviamo-la-ricerca-italiana. Please do. Researchers working at Italian universities and research centres could do with your support. 

Letter to Nature by Parisi et al.

We call for the European Union to push governments into keeping their research funding above subsistence level. This will ensure that scientists from across Europe can compete for Horizon 2020 research funding, not just those from the United Kingdom, Germany and Scandinavia. Europe's research money is divided between the European Commission and national governments. The commission funds large, transnational collaborative networks in mostly applied areas of research, and the governments support small-scale, bottom-up science and their own strategic research programmes.

Some member states are not keeping their part of the bargain. Italy, for example, seriously neglects its research base. The Italian National Research Council has not overseen basic research for decades, being itself starved of resources. University funding has dwindled to a bare minimum. The ministerial initiative known as PRIN (Research Projects of National Interest) has been defunct since 2012, apart from a few limited programmes for young researchers.

This year's PRIN allocation of a 92-million (US$100-million) funding call to cover all research areas is too little, too late. Compare this with the annual French National Research Agency’s allocation of up to 1 billion, or with Italy's 900-million annual contribution to the EU Seventh Framework Programme that ran in 2007–13. That resulted in a net annual loss of 300 million for Italian science.

To prevent distorted development in research among EU countries, national policies must be coherent and guarantee a balanced use of resources.

Would your department refuse to host the recipient of a very competitive post-doctoral award?

Suppose that your department were given the chance to host the recipient of a very competitive post-doctoral award. That award would pay 95% of the salary of the post-doctoral researcher, who also leads a project funded in 2016 (worth 185,373.66€) and one funded in 2015 (worth 222,568.50€). I am fairly confident that your department would welcome that award- and grant-winning post-doctoral researcher with open arms.

This is not what has happened to Vincenzo Dimonte, an Italian set theorist who is presently a post-doctoral researcher at the Kurt Gödel Research Center for Mathematical Logic in Vienna. Dimonte was one of the three recipients in the field of mathematics  of a prestigious and competitive Rita Levi Montalcini award for 2016. In his application for the award, Vincenzo Dimonte gave a ranked list of five three mathematics department in Italy that were willing to host him, the top one being the Department of Mathematics at the Politecnico di Torino. I presume that he even enclosed a letter from someone at that department saying that they were willing to host him. The choice of Turin as top location in his list was natural since Turin hosts a group of top-class set theorists Andretta, Viale, Motto Ros and Camerlo (who is actually at the Politecnico).

However, when Vincenzo Dimonte won the grant, the department twice refused to host him! Of course, he'll go down his own list and I trust that one of the four other destinations he chose will actually welcome him. The fact remains that such decisions are hard to understand when viewed from a purely scientific perspective and may have a negative impact on the future career of someone who has been deemed to be worthy of a top award for young researchers in Italy.

Comments of the European research environment in logic and computation (contribution by Joost-Pieter Katoen and Wolfgang Thomas)

This is the last piece I received in response to my call for opinions on the report on logic activities in Europe that Yuri Gurevich wrote in 1992.

Joost-Pieter Katoen and Wolfgang Thomas discuss the sections of Yuri's report devoted to the European research environment (funding, research centres and other issues) related to logic in computation. You can read their contribution here. Thanks to Joost-Pieter and Wolfgang  for taking the time to write this piece and for allowing me to share it on this blog. Enjoy it!

Andris Ambainis has kindly allowed me to post on this blog the obituary of Rūsiņš Freivalds he wrote for the February issue of the Bulletin of the EATCS. It is a fitting tribute to the importance of Rūsiņš's  lifetime work for TCS in general and for Latvian CS. 

Rūsiņš Mārtiņš Freivalds (1942-2016)

Rusins Freivalds, one of European pioneers of theoretical computer science, passed away on January 4, 2016 at the age of 73.

Freivalds was born on November 10, 1942 in Cesvaine, Latvia. He studied at the University of Latvia and, during his studies, he had an opportunity to spend two years in Novosibirsk, one of leading theoretical computer science research groups in the Soviet Union. There, he started working with Boris Trachtenbrot, one of leading Soviet computer scientists, who supervised his Ph.D. dissertation (defended in 1971 at Novosibirsk State University).

Freivalds is best known for his probabilistic algorithm for testing matrix multiplication, invented in 1977 (https://en.wikipedia.org/wiki/Freivalds'_algorithm). Freivalds' discovery was that, given the result of matrix multiplication, one could check its correctness substantially faster than the time for multiplying the matrices with the best algorithm that is known. Freivalds' algorithm was also one of the first probabilistic algorithms which were faster than deterministic algorithms.

Freivalds' algorithm became an inspiration for other researchers who started studying probabilistic algorithms. In particular, Turing Award winner Manuel Blum mentioned it as an important inspiration in his 1995 Turing Award lecture. Now, Freivalds' algorithm is a part of textbooks on probabilistic algorithms and is taught in many universities.

More generally, Freivalds was one of the first to study probabilistic algorithms and to compare the power of algorithms that use random coin flips with algorithms that do not use randomness. His focus was on finding situations in which one could prove that randomness increases the computational power. For example, Freivalds showed that there is a language that can be recognized by a probabilistic 2-way finite automaton but not by a deterministic 2-way finite automaton. He also showed similar results for 1-way automata with multiple heads, pushdown automata and other computational models. Freivalds’ research in this direction in 1970s and 1980s was among the first results of this type.

Freivalds was interested in many research topics and published over 200 research papers. Another major research interest of Freivalds was inductive inference - a mathematical theory which models the process of learning on an abstract level, using computability theory.

Starting from late 1990s, Freivalds worked on quantum computing and quantum automata. Together with Andris Ambains, he showed that quantum automata can use exponentially less space than probabilistic automata. Most recently, he invented ultrametric automata, a model of automata with p-adic transition probabilities, winning a Best Paper Award at Turing-100 conference in Manchester.

Freivalds supervised 19 Ph.D. dissertations and a number of M.Sc. and B.Sc. theses, including Andris Ambainis (known as a leading quantum computing expert) and Daina Taimina (known for her crocheted models of hyperbolic planes). He was very active in introducing undergraduate students to theoretical computer science and bringing them to research conferences, teaching them to enjoy both research and cultural events (for example, opera or popular science museums).

A number of those undergraduates went on to do their Ph.D., either with him, or other faculty members at the University of Latvia or different universities abroad (including Berkeley, Yale, University of Maryland and University of Waterloo).

Freivalds was an excellent teacher and popularizer of theoretical computer science in Latvia. He was an engaging lecturer who was keen on showing connections between different subfields of mathematics and theoretical computer science. In 2006, University of Latvia students voted him to be the "Teacher of the Year" for all of the natural sciences. Through his teaching and student supervision, he left a major influence on theoretical computer science in Latvia.

Freivalds was highly recognized both in Latvia and internationally. In 2003, he received the Grand Medal of the Latvian Academy of Science (the highest Latvian award for lifetime achievement in research). Freivalds was a member of Academia Europeae and gave a number of invited talks at highly recognized international conferences (such as ICALP - International Colloqium on Automata, Languages and Programming and MFCS - Mathematical Foundations of Computer Science).

Viewpoints on “Logic activities in Europe”, twenty years later

This is the third post related to the viewpoints I commissioned on the report on logic activities in Europe that Yuri Gurevich wrote in 1992.

In case you are interested, you can read my viewpoint contribution (pdf file) that will serve as a preface to the pieces by Thomas Henzinger, Joost-Pieter Katoen and Wolfgang Thomas, and Moshe Vardi. All the contributions will appear in the February 2016 issue of the Bulletin of the EATCS.