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).

Tuesday, April 04, 2017

18 postdoctoral positions at the Gran Sasso Science Institute

The Gran Sasso Science Institute offers 18 postdoctoral positions for research activity in Physics, Mathematics, Computer Science and Social Sciences.
Applicants must hold a PhD degree or an equivalent qualification. 

The research grants are awarded for two years and their yearly amount is € 36.000,00 gross. 

The application must be submitted through the online form available at by May 15, 2017 at 6 p.m. (Italian time zone).

For more information, please consult the Call for Applications at or write an email to

A description of research in computer science at GSSI is available here

Feel free to share this announcement as you see fit.

Saturday, April 01, 2017

The faculty is the university: The case of IMT Lucca

The physicist Isidor Isaac Rabi famously told President Eisenhower that "the faculty is the university." This is a quote I like to use when discussing with university administrators and I was reminded of it these days while reading opinions aired by several Italian academics on IMT Lucca, an Italian centre of advanced study and an international PhD school.

IMHO, a recent case of possible plagiarism involving an IMT graduate hasn't been handled well at all by the top management of that institution. However, to my mind, this event should not be used to debase the excellent work that our colleagues have done and are doing at that institute, which attracts to Italy and trains a good number of high-quality PhD students from abroad, and conducts cutting-edge research in its areas of interest. In fact, I do believe that schools of advanced study such as IMT can play an important role in the academic environment in Italy by attracting talent from abroad and nurturing Italian young researchers within an international research environment. IMHO, the variety those schools add to higher education in my native country is beneficial.

I would definitely encourage my (former) students to take up a PhD or a postdoctoral position within the SysMA group, to work with Rocco De Nicola, Mirco Tribastone and the young researchers in that group, five of whom are from outside Italy. I would also point people interested in control and dynamical systems to the DYSCO group, led by Alberto Bemporad.

These are just two examples from areas that are close to my own research interests. However, the quality of the faculty and of the postdocs and students at IMT is consistently high. I have had the pleasure of giving lectures on basic research skills to IMT students of a varied background, including students in cultural heritage, and thoroughly enjoyed interacting with them.

Summing up, my message to the colleagues who are currently forming an opinion on IMT Lucca based on the actions of its management is simple: "The faculty is the university." Look carefully at the (IMHO, excellent) work done by our colleagues working at that institute and form an opinion based on it, not on mediatic noise.

Wednesday, March 22, 2017

Accepted papers at LICS 2017

The list of accepted papers for LICS 2017 is now available at Thanks to Joel Ouaknine and his PC for their work in selecting such a mouth-watering list of papers!

If you have not done so already, go ahead and register for the conference now. We strongly encourage prospective participants to register, and to make their travel and accommodation plans ASAP. Iceland gets literally fully booked early during the summer months.

Tuesday, March 21, 2017

Opinions on the ERC after ten years

I am collecting some opinions about the European Research Council (ERC) from researchers who have received funding from it, and from some who have not.

What is your overall opinion on the ERC? Do you think that it is good for European research?

My interest in this matter started because the ERC is ten (and so it might be a good time to draw a preliminary assessment of its impact on the European research environment) and was piqued by the opinions aired by the Italian physicist Sylos Labini who claimed that the ERC has become the main problem in European research funding. He says that there are three main problems with the ERC.
  1. The first is that it uses "research excellence" to mask political choices.
  2. The second is that rewarding today's excellence does nothing to support the excellence of tomorrow. Moreover, one does not reward excellent research by giving money to the top 5% of those who apply. 
  3. The third is that the ERC gives a bad example to national funding agencies in Europe, who also reward excellence. 
See also, where Sylos Labini makes a cameo appearance in this paragraph:

But some chafe at the singular focus on excellence. Countries in southern Europe have cut their research budgets during the economic crisis, and now ERC is further weakening these countries by essentially redistributing their EU contributions to the research powerhouses in the north, says Francesco Sylos Labini, a physicist at the Enrico Fermi Center in Rome. And it’s not just the money: “The few Italian researchers that get an ERC grant go to Germany or another country to do their research,” he says.

I do not a long piece of text. Just a few lines would do. I'd be grateful if you could contribute to this discussion by posting your comments.

You might also wish to read Helga Nowotny's short piece entitled ERC---the next ten years.

Monday, March 13, 2017

Rogers Hollingsworth on Major Discoveries of the American System of Science

Recently, I have been reading a fairly long study by historian Rogers Hollingsworth on what makes research organizations produce major discoveries. This talk he gave at the NSF summarizes some of the findings in that article. From around minute 50 in the presentation, the speaker presents some thoughtful closing comments on the current state of funding for basic science and on the effects that the involvement of politicians in making decisions on how to allocate that funding, and in monitoring and auditing the work of scientists, can have on science. For the little that it is worth, I found those thoughts worth mulling over.

Friday, March 10, 2017

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

In this post, I mentioned that a paper by Arash Rafiey, Jeff Kinne and Tomás Feder claiming a solution to the Feder-Vardi  dichotomy conjecture appeared on the arXiv on the 11th of January. The result in that paper was also covered by Lance Fortnow in this blog post.

We now have another preprint, A dichotomy theorem for nonuniform CSPs (71 pages) by Andrei Bulatov, claiming a solution to this long-standing conjecture. (Thanks to Moshe Vardi for pointing this paper out to me.) Not surprisingly, Andrei's paper  uses "the algebraic approach that associates to every relational structure its (universal) algebra of polymorphisms."

I am not an expert on this topic, but I hope that those who are (and especially the prime movers behind the universal algebraic approach to the problem) will stop what they are doing, read this paper carefully and vet its correctness,

I reiterate what I wrote in my earlier post: "If the technical content of the paper is found to be correct by the community working on CSPs after careful peer review, this is a truly major result."

The Feder-Vardi  dichotomy conjecture seems ripe for a solution. We now have two papers, claiming a solution to that conjecture, that use very different techniques. I hope that they are both right and that the tools developed in those articles will find application in the solution of other problems.

Wednesday, March 01, 2017

Registration for LICS 2017 is now open

We are happy to inform you that registration for LICS 2017 and affiliated workshops is open. You can register for the conference and/or its seven co-located workshops by following this link.

As you will see, due to the pressure of the tourist industry (which has increased enormously since we made the bid for hosting the conference in 2015), we are forced to have Friday, 7 April, as early registration deadline. We strongly encourage prospective participants to make their accommodation and travel plans as early as possible, and the date for the early registration is meant to entice them to do so.

As you will see, the early registration fees for the conference are as follows:
  • Early registration fee (members of ACM, ACM SIGLOG, ASL, EATCS or IEEE): 64,000 ISK
  • Early student registration fee: 46,000 ISK
  • Early registration fee (others): 88,000 ISK
The regular registration fees include the cost of the rooms, technical equipment, four lunches (one per conference day), eight coffee breaks (two per conference day), welcome reception and conference dinner at Kolabrautin (three course meal with three glasses of wine per participant). The student registration fees include all the above items, apart from the conference dinner.

In order to meet ACM regulations, the registration fee for members is 25% cheaper than for non-members. We therefore strongly encourage prospective participants who are not members of the ACM, ASL, EATCS or IEEE to join one of those associations. When choosing which association to join, consider the following things:
  1. The EATCS annual membership fee is of 30€. (For students, that would give a two-year membership.) The EATCS sponsors the Kleene Award at LICS 2017 and its Bulletin of the EATCS is published in an open-access form.
  2. Information on ACM SIGLOG membership is available here. There is no need to have a separate ACM membership in order to join SIGLOG. 
  3. The ACM and the IEEE already take 36% of the registration fees and provide no financial sponsorship for the conference, apart from 100K ISK that were kindly offered to us by our friends in the Icelandic Section of the IEEE. 
  4. ACM professional membership costs 99 USD. 
  5. Membership of the IEEE Computer Society costs 60 USD.
  6. A discounted introductory rate for members of the ASL  is available to new regular members of the Association for the first two consecutive years of membership (US$47 in 2017 and 2018).
The LICS 2017 Organizing Committee hopes that this information helps and looks forward to welcoming you in Reykjavik for LICS 2017 and its seven affiliated workshops.

Sunday, February 26, 2017

Ten PhD positions at the Gran Sasso Science Institute

The Gran Sasso Science Institute (GSSI), founded in 2012 in L’Aquila (Italy) as Center for Advanced Studies of the National Institute for Nuclear Physics (INFN) and then established in March 2016 as a School of Advanced Studies providing post-graduate education, offers 40 PhD fellowships for the academic year 2017/18.
Amng others, the GSSI invites applications for 10 fellowships in  “Computer Science”, with emphasis on algorithmics, formal methods for concurrent systems, and software engineering. The official language for all PhD courses is English.

The fellowships are awarded for three years and their yearly amount is € 16,159.91 gross. All PhD students have free accommodation at the GSSI facilities and use of the canteen.

The application must be submitted through the online form available at by 31st May 2017 at 18.00 (Italian time zone).

For more information, please consult the Call for Applications at or write an email to or call +39 0862 4280262.

Tuesday, February 21, 2017

Computer Science at Reykjavik University looks for a new dean

I hope that readers of this blog will consider  applying for this position and join the School of Computer Science at Reykjavik University. Come and help us shape the future of CS research and teaching in Iceland!

Reykjavik University seeks an ambitious leader to carry out the development of a growing School of Computer Science. The dean is responsible for administrative affairs as well as for leading the faculty's academic agenda. The dean reports to the Rector of Reykjavik University and is a member of the university's executive committee.

We seek candidates that have:
  • Strong strategic vision and the ability to shape and lead a team of faculty members and staff
  • Doctorate in computer science or related subjects
  • Academic teaching and research experience
  • Management, operations and leadership experience
  • Experience from industry or collaborations with industry
  • International experience

Reykjavik University's School of Computer Science provides education and research in computer science, software engineering and related subjects. The School offers BSc, MSc and PhD degrees. External accreditation committee for doctorate studies assessed the school to be the strongest in Iceland in its field and one conducting top-level international research ( The school has around 850 enrolled students and nearly 30 faculty and staff members.

For further information, please contact Ari Kristinn Jónsson, Rector ( and Sigríður Elín Guðlaugsdóttir, Executive Director of Human Resources ( tel: +354-599-6200.
Applications should be submitted before March 15th, 2017, through our applications website:

The role of Reykjavik University is to create and disseminate knowledge to enhance the competitiveness and quality of life for individuals and society, guided by good ethics, sustainability and responsibility.

There are four schools within the university; School of Business, School of Computer Science, School of Law and School of Science and Engineering. Education and research at RU are based on strong ties with industry and society. We emphasize interdisciplinary collaboration, international relations and entrepreneurship. Reykjavik University currently has around 3600 students and 240 employees.

Friday, February 10, 2017

An Interview with Thomas Henzinger, President of IST Austria

The Institute of Science and Technology Austria (ISTAustria) is a young international institute dedicated to basic research and graduate education in the natural and mathematical sciences, located in Klosterneuburg on the outskirts of Vienna. Our colleague Thomas Henzinger has been the president of the institute since its birth, and I thought that it might be interesting for the readers of the Bulletin of the EATCS and of this blog to hear about the development of IST Austria and his opinions on how to create an excellent research institution.

I interviewed Thomas Henzinger (abbreviated to TH in what follows) via email and present his answers to my questions in what follows. 

LA: Could you briefly introduce IST Austria, its aims and its current state of development? 

TH: The Institute of Science and Technology (IST) Austria was founded in 2006 with the goal to build in Austria a world-class institution for basic research and graduate education in science. Currently we are half-way towards our goal of 90 research groups in biology, physics, chemistry, mathematics, and computer science.

LA: As far as I know, IST Austria only started its operations in 2009. It already underwent a successful,  international evaluation in 2011 and has grown remarkably since then. In your opinion, which strategic decisions have been crucial in making IST Austria a high-quality research institute in such a short period of time and in attracting top-class scientists at various stages of their careers to it?

TH: The most important decision of the Austrian government was to start IST Austria from scratch, independent of any existing institution, and to give the Institute maximal freedom in designing itself.  Whenever we take a design decision at IST Austria, we consider primarily one criterion: how can we best compete for the most promising young faculty and the most talented PhD students in the world?  Three of our most important design decisions, all guided by this criterion, were: (1) We hire all young faculty on a tenure track, giving them both independence and the opportunity to be promoted to a full professorship, based solely on performance. (2) We never assign open faculty slots to research topics or scientific disciplines, but always try to offer our positions to the most promising candidates we see, independent of their field. (3) All PhD students are admitted centrally and must complete a multidisciplinary curriculum and rotation projects with several professors before they embark on their thesis research.

LA: So far, which aspects of the development of IST Austria are you most proud of?  How would you like to see IST Austria grow in the near future? Do you think that the institute  will expand its research in computer science and, if so, how?

TH:  I am proudest of the fact that 30 of our 45 professors are funded by the European Research Council.  I believe that relative to our size, this makes us the most successful institution in Europe. Among our 45 current professors, there are 8 computer scientists. We hope to double both numbers over the next  10 years.

LA: I recently watched the video of the panel discussion "IST Austria: On the Way to the Top: What Makes a Research Institution Excellent?'', which you chaired, on YouTube. It was truly inspirational. However, since you were running short of time, you did not get a chance to express your views on the topic and I, for one, would be very interested in hearing them. So, in your opinion, what makes a research institution excellent? Would the advice you would give to a computer science department in a European university that strives for excellence be any different?

TH:  Most science administrators agree that the key to excellence is the principle "hire the best scientists and leave them alone." It is easy to advocate this principle, but it is difficult to implement it. The temptation to think strategically top-down -to focus on research areas when hiring professors, on research projects when hiring students, on industrial and societal needs when asking for more funds- is very hard to resist.  But giving in to that temptation usually means leaving the quickest path to scientific excellence.

LA: To your mind, what is the role of PhD education in achieving research excellence? Would you have any advice to share with us on how to run an international PhD granting institution in Europe that is capable of attracting very strong students? 

TH: Attracting top PhD students from all over the world is critical because top students attract top professors. In fact, in my experience it is more difficult to attract top students: they are often more "brand driven" than professors, and it takes a long time for an institution to build up a world-wide reputation that trickles down to undergraduates looking for PhD programs. I wish I had a quick solution for this problem.

LA: You have been the President of IST Austria from its inception. This must be more than a full-time job. However, at the same time, you have managed to remain very active in research, pursuing new avenues and maintaining a research group. How did you do so? Is there any "secret" you'd like to share with us?

TH:  It is difficult to "context switch" between administrative and scientific problems. But the opportunity to talk with my students and postdocs almost on a daily basis is what keeps me sane. It is important also because it allows me to see the Institute and its administration from the "other" side, and because it  gives me greater credibility when trying to recruit faculty.


Tuesday, January 31, 2017

Call for expressions of interest for permanent positions at the Gran Sasso Science Institute

I have been asked to distribute this call. The Gran Sasso Science Institute is a new, ambitious international centre for advanced studies and PhD school. Give this opportunity a thought. 

Gran Sasso Science Institute - Computer Science Area

Expression of Interest for Faculty Positions

Gran Sasso Science Institute (GSSI) is a new Center for Advanced studies and PhD School established in L’Aquila (Italy).
The Computer Science Area of GSSI ( invites expressions of interest for permanent positions at the level of Full or Associate Professor, and for tenure track (Ricercatore TD – B), and temporary (Ricercatore TD – A) research assistants. Highly qualified candidates with a strong research background in the following fields: cryptography, network security, algorithms, and software engineering are encouraged to apply. The Institute is particularly interested in (potential) leaders of multi-disciplinary research groups in the above fields.
Candidates must have an excellent record of publications, a clear potential to promote and lead research activities, and a specific interest in teaching at the postgraduate level to skilled students recruited internationally.

Applicants should submit their expression of interest by sending
  • a motivation letter in which also the position(s) of interest are specified.
  • a curriculum vitae
  • a list of publications,
  • a brief research statement.
Applications (and questions regarding the application process) must be submitted in electronic form, preferably by April 1st 2017, to

Please note that this is not a permanent job vacancy advertisement. The expressions of interest received will contribute to the decision of the Gran Sasso Science Institute whether or not to open official calls, their number and the selection procedures.


1- Duties
Teaching post-graduate courses, leading internal seminar and tutoring PhD students. All activities are in English.
2- Salary
The salary will be determined on a personal basis, also taking into account past positions covered abroad. Indicative figures of the gross amount for starting (minimum) salary are:
  • Professor (prima fascia) € 72.431
  • Associate Professor (seconda fascia) € 50.831
  • Assistant Professor, tenure track (ricercatori TD – B) € 34.898
  • Assistant Professor, no tenure track (ricercatori TD – A) € 34.898
Net income may vary depending on income taxes, local taxes, retirement plan, health care deduction and tax exemptions. Professors who have held a tenured position outside Italy for more than three years (at the corresponding level) might be eligible for a partial recognition of past services, depending on specific legal constraints.

Tuesday, January 24, 2017

EATCS Award 2017 to Éva Tardos

The EATCS is proud to announce that the EATCS Award Committee consisting of Fedor Fomin (chair), Christos Papadimitriou and Jean-Eric Pin has selected Professor Éva Tardos (Cornell University, USA; as the recipient of the EATCS Award 2017. Eva is the first female theoretical computer scientist who receives the EATCS Award.

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

The EATCS Award carries a prize money of 1000 Euros and will be presented at ICALP 2017, which will take place in Warsaw (Poland) from the 10th till the 14th of July 2017.

Sunday, January 22, 2017

Report on the rest of SOFSEM 2017 (guest post by Ignacio Fábregas)

I continue my notes on this year's SOFSEM conference where I left them. On Wednesday, I attended the tutorial session by Andrew Butterfield on Unifying Theories of Programming (UTP), a paradigm introduced by C.A.R. Hoare. Broadly speaking, UTP combines denotational, operational and algebraic semantics in a unified framework for both the formal specification and implementation. It is almost as there was no distinction between syntax and semantics. Andrew Butterfield also showed us  his tool UTP2, programmed in Haskell, and how the library for UTP in the Isabelle theorem prover works. 

One important part in any conference is to be able to discuss with other colleagues and experts about interesting papers. On Wednesday I missed the keynote talk by Jakko Hollmen about Predictive Analytics because I was talking about some papers with colleagues. (I found that to be a valid excuse to miss a talk in a conference!) Also, on Wednesday we had the social programme: an excursion with a guide around the city centre of Limerick and the conference dinner in the Bunratty Castle. Inside the castle we not only enjoyed a typical Irish dinner but also an entertainment program. It was a dinner with a medieval flavour because of the place but also because of the show we saw and the way we ate. We had a broth, pork ribs and chicken... But without forks! So we ate with our hands while listening to some typical Irish songs performed by the very talented people of the Bunratty Castle.

That's not all that happened on Wednesday. The organization had a surprise for us: since the lunch break was two hours long, during the second hour we had a talk about music and computers. Inside the Department of Computer Science in Limerick there is the Digital Media & Arts Research Centre, and the organization took advantage of this fact in order to propose them to give 3 talks: one on Wednesday and two on Thursday. The first talk was done by Mikael Fernström (, who explained us his work. He uses computers in order to produce new sounds (frequencies that a physical instrument wouldn't be able to make) and algorithms in order to create music for "things". As an example, he created a piece that took some variables from meteorological data so we could listen to how the weather in Ireland sounds.

On Thursday, in this special sessions, Giuseppe Torre ( showed us his work, where he uses computers to represent art. For example, his work 'AI PRISON' is a program in C++ that outputs '0' unless the technological singularity in Kurzweil's sense (or 'Terminator' sense) appears. It is exposed in the BLITZ Contemporary Art Gallery in Malta. Finally, Kerry l. Hagan ( played some of his musical works. Again, the use of computers is the cornerstone. She uses a program that allows her to program and compose the music she is going to play. This three artistic sessions where a really nice touch from the organization.

Back to the science, on Thursday we started with a keynote talk by Óscar Pastor López about Model-driven Development. The idea is that developers should be freed from programming concerns and be able to concentrate on guaranteeing that the final software product corresponds to what the company asked for. There are two basic notions in this field: capability and the Model Driven Architecture. The first one is especially used at the earliest steps of a software process in order to characterize the relevant modelling components to be specified. Whereas the Model Driven Architecture is used in the definition of the desired software process in order to structure the development from requirements to code.

Afterwards I attended the tutorial by Cristina Seceleanu about verification and test-case generation for Automotive Systems. Nowadays a car is developed with more electric components than hydraulic ones. For example, the connection between the steering wheel and the steering control is done by wires and software. This makes mandatory the use of testing in order to verify the correct behaviour of a car. In this field of research tools as UPPAAL are of great use. After the lunch we had the second keynote talk of the day. Paul Spirakis explained us about "programmable matter", which at the beginning seemed a field closest to sci-fi than actual computer science. So, let me explain what I understood, nowadays digital information (as internet) has spread along the world. That information is simply data, which can be manipulated. This vision is focused in our ability to manipulate data, and thus extended to manipulate matter via information-theoretic and computing mechanisms, incorporating information to the physical world. This is inspired in the biological world where living organisms are built by cells and those cells are built by information (DNA). Paul Spirakis explained us how Network Constructions is a promising technique for modelling this idea of "programmable matter". Broadly speaking, Network Constructions is simply a collection of finite-automata that interact randomly like molecules according to the rules of a common protocol.

The last session on Thursday for me was the tutorial session by Louis-Marie Traonouez by Plasma Lab, a statistical model checker (SMC). A SMC and uses less resources than a model checker at the cost of losing certainty. SMCs answers with a confidence level. Plasma Lab is SMC a library written in Java that can be used in tools as UPPAAL. The properties can be described in a form of bounded linear temporal logic (like LTL but with bounds in the length of the paths).

The last keynote talk of SOFSEM 2017 was on Friday and by Igor Walukiewicz. The topic of the talk was automatic verification of recursive programs with thread creation. Although this situation appears in programming languages such as Java, Scala or Erlang it doesn't behave well in automatic verification. For example, reachability is not decidable even for pushdown systems where two threads are communicating over a 2-bit shared variable. Igor Walukiewicz showed us some decidable setting by relaxing the semantics of thread creation operation. The obtaining result might not be very efficient but at least is computable.

Finally, I want to end these notes on SOFSEM by acknowledging the excellent work of the local organization at Limerick. It's true that SOFSEM 2017 didn't start very well in June, but all things considered everything went smooth and fine in Limerick. Also, the organization always tried to add something new to the conference (as those special talks about art and computer science), which is always nice for the participants.

Next year SOFSEM will be held in Austria and my recommendation is to check it out!

Wednesday, January 18, 2017

Report on the first two days of SOFSEM 2017 (guest post by Ignacio Fábregas)

Ignacio Fábregas has kindly sent me this report on the first two days of SOFSEM 2017, which is being held this week in Limerick, Ireland. I hope you'll enjoy reading it.  Many thanks to Ignacio for agreeing to write this guest post.
SOFSEM has always be an atypical conference with a format closest to a Winter School. This year marks a new beginning for the SOFSEM conference, since it's the first time it's held outside the Czech Republic or the Slovak Republic. As Jan van Leeuwen told us in the Welcome Reception on Monday, the goal of the Steering Committee of SOFSEM is to keep the spirit of SOFSEM alive while moving to a more typical format for a computer science conference. The main ingredients are still there: the keynote talks of renowned experts, tutorial sessions and the Student Research Forum; the only main difference is the country (Ireland) and the schedule (instead of having all the keynote talks the first and last day, now they are distributed across the conference days).

The first day of the Conference the keynote speaker was Kim G. Larsen. He told us about Cyber-Physical Systems (CPS), that is, systems combining computing elements with dedicated hardware and software having to monitor and control a particular physical environment. In order to study them, Larsen and his team propose a model-based approach, powered by the use of the tool Uppaal. An example of CPS is the adaptive cruise control for cars, an application where Europe is trying to match U.S. (where the Google Self-Driving car has already been approved by the legislation in several U.S. states) and where the team of Kim Larsen is making advances.

After the keynote talk we had the first parallel sessions: two sessions of the Foundations of Computer Science (FOCS) track and the first tutorial. I went to the FOCS session about Semantics, Specification and Compositionality, mainly because my talk was there :) But, more importantly, there was a talk of Uli Fahrenberg and another by Linda Bordo. Uli talked about behavioural specification theories for most equivalences in the linear-time–branching-time spectrum. He humbly defined his work as "almost" a rewriting of some old and overlooked results. Going back, reading and, most importantly, understanding, old results is a non-trivial exercise that computer science researchers should do more often. On the other hand, Linda talked about link-calculus, as a model that extends the point-to-point communication discipline of Milner’s CCS with multiparty interactions. She used links to build chains describing the flow of information among the agents participating in that interaction. The difficult part comes when deciding both the number of participants in an interaction and how they synchronize.

The second day of conference we had two keynote talks. Axel Legay talked about Software Product Lines (SPL), that is, the families of similar software products built from a common set of features. For example, like the mobile phones that a company as Samsung or HTC produce. He showed us how he and his team formalizes SPLs by means of what they called Featured Transition Systems and how the designed verification algorithms and tools to check temporal properties over them. The second keynote talk was by Marjan Mernik. He told us about Domain-Specific Languages that assist software developers in programming, and some open problems in the field like the lacking of tool support for different Domain-Specific Languages and the difficulties combining them.

Relative to the conference papers, in the FOCS session in Verification and Automated System Analysis we have talks by Mohammad Reza Mousavi, Nataliya Gribovskaya, Zhaowei Xu and Saket Saurabh. I want to highlight Mohammad's talk about the complexity of deriving invertible sequences from finite-state machines. The problem is the following: checking the existence of input/output sequences (UIOs) that identify states of the finite state machine specification (as it's the case of ioco) is PSPACE-complete; so some UIO generation algorithms utilise what are called invertible sequences; these allow one to construct additional UIOs once a UIO has been found. Mohammad and his coauthors studied some optimization problems and their complexity.

And that's all for now. Tomorrow (18 January 2017) we'll have fewer talks since we have the excursion and conference dinner. Also I'm planning to go for one tutorial session by Andrew Butterfield. I'll tell you more on that.

Thursday, January 12, 2017

Has the Feder-Vardi dichotomy conjecture been proved?

The Feder-Vardi dichotomy conjecture (which, as far as I know, stems from this 1998 article) is a celebrated open problem in the study of the complexity of constraint satisfaction problems (CSPs). It states that, for every finite relational structure, the set of all CSPs that can be represented using only relations chosen from that set is either in P or is NP-complete.

A paper claiming a solution to the Feder-Vardi  conjecture appeared yesterday on the arXiv:

Tómas Feder is the third author. (However, I noticed that the order of the authors in the version of the paper Feder posted on his web page is different from the one used in the arXiv version.)

The authors have also posted two videos on YouTube:

If the technical content of the paper is found to be correct by the community working on CSPs after careful peer review, this is a truly major result.

Wednesday, January 11, 2017

Call for Nominations for Scientific Directorship in Algorithms and Complexity at the Max Planck Institute for Informatics

The Max Planck Institute for Informatics in Saarbrücken is seeking nominations for the position of Scientific Member of the Max Planck Society and Director of the Institute. The founding director, Kurt Mehlhorn, will be retiring in the next three years, and the Institute is looking for a new scientific director for the algorithms and complexity department. (More precisely, Kurt will step down as Director on the day a new director joins. He will stay on as a researcher at the Institute.)

Webpage with the details of the call for nominations: (Self-nominations are possible.)