Wednesday, June 14, 2017

Interview with Alexandra Silva, Recipient of the 2017 Presburger Award

The European Association for Theoretical Computer Science (EATCS) established the Presburger Award in 2010. The award is presented each year at 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 2017 Presburger Committee, consisting of Marta Kwiatkowska (chair), Stephan Kreutzer and Jukka Suomela, has selected Alexandra Silva (Senior Lecturer at University College London, UK) as recipient of the 2017 EATCS Presburger Award for young scientists. To my mind, this is a wonderful choice. Alexandra Silva is one of the brightest rising stars within our research community and, in a very short period of time, has established herself as a research leader and a mentor for young researchers, who somehow also finds the time to serve the theoretical-computer-science community in a variety of roles.

I interviewed Alexandra Silva (abbreviated to AS in what follows) via email and present her answers to my questions in what follows. I hope that the readers of the Bulletin of the EATCS will enjoy reading the text of the interview and will find it as interesting as I did. Most importantly, I trust that young researchers and students in (theoretical) computer science will be inspired by Alexandra's example to pursue a career in our exciting field of science.

LA: Alexandra,  first of all, congratulations for the 2017 Presburger Award! I wanted to start by asking you about your background and when you became
interested in computer science.  When did you decide to pursue a PhD and a career in academia? Is there anyone who played an important role in that decision?

AS: I wanted to study mathematics, but my brother convinced me I should do a double bachelor in maths and CS because otherwise I would not get a job :-) I did a Math and CS degree at Universidade do Minho  (Braga, Portugal) and fell in love with the foundations of CS. I decided to pursue a PhD after a very happy research project at the end of my degree supervised by Joost Visser and Jose Nuno Oliveira. I worked very closely with Joost for 6 months and he was a great inspiration in my career and taught me the basic principles of research. Another person who was instrumental was Luis Barbosa: he motivated me to go abroad for a PhD and to ask Jan Rutten to be my advisor.

LA: So far, you have studied and worked in Portugal, the Netherlands and the UK, and have collaborated with researchers in Germany and the US, amongst others. How important has this variety of experiences been for your career development? Do you prefer to work alone or to collaborate with other people?

AS: Working in different countries and being exposed to different cultures has made me a more flexible and resilient person.  This has been very important in my career, also to help me deal with all the rejected papers and grant proposals! :-) I am happy to meet new people and discuss research. When I am excited about a new idea I like to share it with my colleagues and discuss ways to improve it!

LA: Could you tell our readers briefly what your main research interests are today?

AS: These days I am very keen on applications of automata learning in verification. Frits Vaandrager planted the seed in 2011 when I joined Nijmegen and 4 years later I really saw the light and since then have been very excited on working in understanding existing learning algorithms and improving them, using a categorical perspective on their correctness proofs. I am currently exploring connections with my other passion -- Kleene algebra and extensions thereof -- and looking at learning NetKAT specifications from networks. 

LA: These days you are managing a fairly large research group.  Have you found it difficult to become the leader of a group, with the responsibility of managing substantial research grants and of making sure that the young researchers in the group thrive and produce the best work they can? Is there any specific strategy you adopt in managing your group?

AS: I find it very exciting but at the same time the responsibility does overwhelm me at times. I see these super bright young minds and would like to help all of them thrive, in ways other people have helped me in my career. My current strategy is to make sure they know I am always available to talk and help but more importantly I want them to realise they are part of a team and support can come from anyone in that team. We have a slack channel that is very active and in which all issues are discussed -- from completeness of Kleene Algebra to how you can trick image recognition software to think a puppy is fried chicken (credits to Joshua Moerman!).

LA:  I know that you have a strong interest in gender issues and in increasing the number of women in computer science and their visibility within the community. What has been your experience as a young woman in TCS? Do you have any advice to offer to the community in order to attract and retain more talented female students? Did you have any female role model and how important do you think they are in general?

AS: I was very lucky at the beginning of my career and throughout my PhD and post-doc I never felt there was any problem. This was in part due to my advisors -- Jan Rutten, Marcello Bonsangue, and Dexter Kozen -- who were real mentors throughout the years and always made me feel welcome in the research environment of their groups. It was when I became a faculty member that I felt animosity from several male colleagues. One told me that I only got my first faculty job because I was a woman. That day I truly thought it was the end of my career. I survived that incident and the many that followed but it did leave marks and a strong will to avoid others having to go through the same. When Prakash [Panangaden] invited me to join the SIGLOG executive board I saw an opportunity to do something for the community and pushed that we implement anti-harassment policies in SIGLOG conferences and try to foster a welcoming environment for everyone. I am not sure I have any good advice on how to attract female students -- I think as a community we need to strive to create more welcoming environments and start new trends in which being a woman in TCS becomes a normal thing! Catuscia Palamidessi and Marta Kwiatkowska are great female role models and have inspired me at various points me in my career. I have also had many male role models, including yourself, for which I am very grateful!

LA: Finally, you were one of the prime movers in establishing the Logic Mentoring Workshop at LICS. is there any advice you'd give a computer science student with an interest in carrying out research in TCS and working in academia?

AS: Whatever topic you decide to work on, the most important thing is to be excited about it. Happier research is better research, in my opinion. Also, the topic you choose today will not define you in the future: that is the beauty of working in academia, one can change research topic during the years! From a more practical perspective, it is important to have mentors and role models that will help you make the right decisions at important turning points of your career.

Monday, June 12, 2017

Has the Feder-Vardi dichotomy conjecture been proved? (Take 3)

In this post and this one,, I mentioned a paper by Arash Rafiey, Jeff Kinne and Tomás Feder and one by  Andrei Bulatov, claiming a solution to the long-standing Feder-Vardi dichotomy conjecture. Today Moshe Vardi pointed out to me this paper by Dmitriy Zhuk that offers a third proof of that conjecture.

At this point, I think that one can safely say that the dichotomy conjecture is true. Indeed, I find it hard to believe that all the three proofs contain mistakes that cannot be patched. As I wrote in my earlier posts on this matter, I hope all the proofs will be found to be correct by the community and that the techniques used in those articles will find application in other contexts.

Congratulations to the authors of those papers!

Saturday, May 27, 2017

Best paper awards at ICALP 2017

The following papers will receive the best paper awards at ICALP 2017 (source:

  • Best Track A Paper: A. Björklund, P. Kaski and I. Koutis.  Directed Hamiltonicity and Out-Branchings via Generalized Laplacians. 
  • Best Track A Student Paper: E. Lee. Improved Hardness for Cut, Interdiction, and Firefighter Problems. 
  • Best Track B Paper: M. Benedikt, P. Bourhis and M. Vanden Boom. Characterizing Definability in Decidable Fixpoint Logics. 
  • Best Track B Student Paper: F. Reiter. Asynchronous Distributed Automata: A Characterization of the Modal Mu-Fragment.
  • Best Track C Paper: E. I. Ásgeirsson, M. M. Halldorsson and T. Tonoyan. Universal Framework for Wireless Scheduling Problems.
Congratulations to all the award recipients!

It's been another good year for Nordic TCS (best papers at tracks A and C). Of course, we at ICE-TCS are particularly pleased for the Track C best paper award to our ICE-TCS colleagues Eyjólfur Ingi Ásgeirsson, Magnús Már Halldórsson and Tigran Tonoyan. Way to go!

Friday, May 05, 2017

2017 Alonzo Church Award announcement

Gordon Plotkin has kindly shared the 2017 Alonzo Church Award announcement with me. I am happy to post it here and hope that readers of this blog will be enticed to learn about this truly fundamental contribution to theoretical computer science.

The 2017 Alonzo Church Award for Outstanding Contributions to Logic and Computation is given jointly to Samson Abramsky, Radha Jagadeesan, Pasquale Malacaria, Martin Hyland, Luke Ong, and Hanno Nickau for providing a fully-abstract semantics for higher-order computation through the introduction of game models, thereby fundamentally revolutionising the field of programming language semantics, and for the applied impact of these models. Their contributions appeared in three papers:
  • S. Abramsky, R. Jagadeesan, and P. Malacaria. Full Abstraction for PCF. Information and Computation, Vol. 163, No. 2, pp. 409-470, 2000. 
  • J.M.E. Hyland and C.-H.L. Ong. On Full Abstraction for PCF: I, II, and III. Information and Computation, Vol. 163, No. 2, pp. 285-408, 2000. 
  • H. Nickau. Hereditarily sequential functionals. Proc. Symp. Logical Foundations of Computer Science: Logic at St. Petersburg (eds. A. Nerode and Yu.V. Matiyasevich), Lecture Notes in Computer Science, Vol. 813, pp. 253-264. Springer-Verlag, 1994. 
Description of the Contribution 

These papers made two fundamental contributions to our understanding of programming languages and logic. First, they provided signi ficant insight into the longstanding and fundamental "full abstraction problem" for the paradigmatic higher-order language PCF by giving a compositional semantic account of sequentiality, via an elegant cartesian-closed category of games and strategies. In the mid-1970s Milner posed the full-abstraction problem for PCF and Plotkin showed the difficulty of the problem, which essentially lies in the fact that the standard Scott-Strachey model permits non-sequential functions, although PCF itself is sequential.

The papers constructed models for PCF from games, leading to the first fully abstract models of PCF whose construction made no reference to the syntax of PCF. The elements of the models are strategies for certain kinds of interactive dialogues between two players (or between system and environment). These dialogue games are required to follow certain conventions concerning when questions are posed or answered; these conventions reflect constraints on the information available to the players of the game. The papers give new insight into the fundamental work in higher-type recursion theory of such logicians as Kleene, Gandy, Normann, and Hyland.

Second, and perhaps more importantly, game semantics has provided a new framework for the semantics of programming languages. Games can be used as a flexible and modular modelling tool, as a wide variety of programming language features can be understood as corresponding to different restrictions placed on allowed strategies. Thus there are fully abstract games models for call-by-value and call-by name languages; for languages with state, with control, with references, with exceptions, with nondeterminism, and with probability; and for concurrent and mobile process languages. In this way, game semantics has changed the landscape of programming language semantics by giving a unified view of the denotational universes of many different languages. This is a remarkable achievement that was not previously thought to be within reach.

Techniques developed in game semantics have found their way into a wide variety of applications. For example, they have provided tools for the verification of a range of computational systems, such as reactive systems of timed and hybrid automata, higher-order and mobile processes, and model-checking higher-order programs. There has also been significant influence on other areas, for example, static program analysis, type systems, resource-sensitive compilation, and compiler certification. All of these developments can be traced from the initial work of Abramsky, Jagadeesan and Malacaria, of Hyland and Ong, and of Nickau.

The 2017 award will be presented at the 26th Computer Science Logic (CSL) Conference, the annual meeting of the European Association for Computer Science Logic. This will be held August 20th{24th, 2017, at Stockholm University, Sweden.

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 Godel Society (KGS). The award is for an outstanding contribution represented by a paper, or small group of papers, within the past 25 years; this is the second such award. The 2017 Award Committee consisted of Catuscia Palamidessi, Gordon Plotkin (chair), Natarajan Shankar, and Moshe Vardi.

Thursday, May 04, 2017

Call for participation: LearnAut at LICS 2017

The organizers of the Learning and Automata (LearnAut)  workshop, which is co-located with LICS 2017, have asked me to distribute the appended call for participation. 

The full list of workshops is available at
The early registration deadline is tomorrow
Please distribute this call to your students and research collaborators, as you see fit.



Learning and Automata (LearnAut) — LICS 2017 Workshop
June 19, Reykjavik (Iceland)
Early registration: May 5th

Grammatical Inference studies machine learning algorithms for classical recursive models of computations like automata and grammars. The expressive power of these models and the complexity of associated computational problems are a major research topic within theoretical computer science. This workshop aims at offering a favorable place for dialogue and at generating discussions between researchers from these two communities.

The following papers have been accepted for oral presentation:

  • Enes Avcu, Chihiro Shibata and Jeffrey Heinz: Subregular Complexity and Deep Learning
  • Alexander Clark: Strong learning of Probabilistic Context-Free Grammars from Strings
  • Nathanaël Fijalkow: Bisimulation on Distributions for Markov Decision Processes
  • Oded Maler and Irini-Eleftheria Mens: On Learning Symbolic Automata over Boolean Alphabets
  • Ariadna Quattoni, Xavier Carreras and Matthias Gallé. Scalable Spectral Learning of Automata through Maximum Matching
  • Rick Smetsers: Grammatical Inference as a Satisfiability Modulo Theories Problem

In addition, the papers accepted for poster presentation are:

  • Giovanni Bacci, Giorgio Bacci, Kim Guldstrand Larsen and Radu Mardare: On the Metric-based Approximate Minimization of Markov Chains
  • Simone Barlocco and Clemens Kupke: Automata Learning: A Modal Logic Perspective
  • Michael Bukatin and Jon Anthony: Dataflow Matrix Machines as a Model of Computations with Linear Streams
  • Kaizaburo Chubachi, Diptarama, Ryo Yoshinaka and Ayumi Shinohara: Query Learning of Regular Languages over Large Ordered Alphabets
  • Joshua Moerman: Learning Product Automata
  • Tianyu Li, Guillaume Rabusseau and Doina Precup: Neural Network Based Nonlinear Weighted Finite Automata
  • Alexis Linard, Rick Smetsers, Frits Vaandrager, Umar Waqas, Joost van Pinxten and Sicco Verwer: Learning Pairwise Disjoint Simple Languages from Positive Examples
  • Xiaoran Liu, Qin Lin, Sicco Verwer and Dmitri Jarnikov: Anomaly Detection in a Digital Video Broadcasting System Using Timed Automata
  • Guillaume Rabusseau and Joelle Pineau: Multitask Spectral Learning of Weighted Automata
  • Michal Soucha and Kirill Bogdanov: Efficient Active Learning with Extra States

The following top researchers will be invited speakers at LearnAut:
  • Kim G. Larsen (Aalborg University)
  • Mehryar Mohri (New York University & Google Research)
  • Alexandra Silva (University College London)

If you have not registered yet to the workshop, and if you are interested by its program, we strongly recommend you to do it as soon as possible ( The early registration deadline is on May 5th.

Pressures on accommodation possibilities are high, the sooner you book one the better it is (a lot of hotels are unfortunately already full).

Looking forward to seeing you at Reykjavik!

Friday, April 14, 2017

Public service announcement for LICS (workshop) participants

This is a public service announcement. If you plan to attend a LICS 2017 workshop and/or the main conference, and you have not booked your flight and accommodation yet, I strongly suggest that you do so ASAP. Iceland is a very hot holiday destination these days and it becomes fully booked soon, especially during the summer months. We already have about 160 registered participants for the conference and accommodation is disappearing at a rate of knots.

Friday, April 07, 2017

Ten PhD positions in CS at the Gran Sasso Science Institute

The Gran Sasso Science Institute (GSSI -, a recently established international PhD school and a Centre for advanced studies in L'Aquila (ITALY), offers 10 PhD positions in Computer Science (CS).

The PhD program in CS is mainly concerned with heterogeneous distributed systems and their interactions. Different perspectives are offered to provide students with the necessary tools for the design, the implementation, the management and the use of distributed systems. The main research areas of interest are:
- Efficient algorithms for communication networks and social networks;
- Formal methods for systems correctness and analysis;
- Software engineering for efficient and resilient applications.

Apart from pursuing their own research studies, the successful candidates will have the opportunity to cooperate with members of the research group and of the Scientific Board, as well as with the frequent guests of the Institute. Detailed information about the CS research group and about the activities for the PhD program in CS can be found at

The fellowships are awarded for three years and their yearly amount is € 16.159,91 gross. Moreover all PhD students:
- will have free accommodation at the GSSI facilities and luncheon vouchers;
- will have tuition fees waived;
- will be covered by insurance against accident and/or injury.

The application must be submitted through the online form available at and must be accompanied by the curriculum vitae of the applicant, and by a letter of motivation describing expertise and general research interests together with future plans and reasons for having chosen GSSI for PhD studies.

The deadline for application is: 31st May 2017 at 18.00 (Italian time).