Tuesday, June 21, 2016

EATCS Bulletin Issue 119 is available online

The June 2016 issue of the Bulletin of the EATCS is now available on line. If you prefer, you can download a pdf with the printed version of the Bulletin. As usual, thanks to the support of the members of the EATCS, the Bulletin is open access.

This issue of the Bulletin  features the following columns:
Some of you might also be interested in advice to young researchers from Michael Fellows and other Fellows of the EATCS, and in interviews with the recipients of the Gödel Prize 2016 and of the first Alonzo Church Award.

Thanks to Kazuo Iwama, the editor in chief of the Bulletin, and the EATCS Secretary Office for their work on another excellent issue of the Bulletin.


Monday, June 06, 2016

One PhD or post-doctoral position at the School of Computer Science, Reykjavik University


Theoretical Foundations for Monitorability

School of Computer Science, Reykjavik University
One PhD or Postdoctoral Position


Applications are invited for one PhD or postdoctoral position at the School of Computer Science, Reykjavik University.  The position is part of a research project funded by the Icelandic Research Fund, under the direction of Luca Aceto (Reykjavik University), Adrian Francalanza (University of Malta) and Anna Ingolfsdottir (Reykjavik University). The general aim of the project is to develop further the theoretical foundations of monitorability for fragments of variants of Hennessy-Milner logic with recursion/modal mu-calculus.

The project work will build on the RV 2015 paper by the co-proposers (http://dx.doi.org/10.1007/978-3-319-23820-3_5), and on the experience developed during their previous work on runtime verification and on the tool detectEr (http://www.cs.um.edu.mt/svrg/Tools/detectEr/). The goals of the project will be:

  • to explore more stringent conditions for detection than the ones considered in the RV 2015 paper and study whether this has any effect on the monitorable subset of the logic;
  • to investigate the monitorability of the logic with respect
    to instrumentation set-ups other than the one used in the RV 2015 paper;
  • to extend our results from the RV 2015 paper to the setting of real-time systems, modelled as timed automata, and to a real-time variant of Hennessy-Milner Logic with recursion;
  • to understand how existing notions of monitorability relate to the one formulated in the RV 2015 paper, thereby consolidating disparate concepts of monitorability;
  • to investigate extensions to monitorability that incorporate notions
    of enforceability; and
  • to apply the results of the theoretical work in the construction of a prototype software tool for the runtime analysis of systems.

The successful candidates will benefit from, and contribute to, the research environment at the Icelandic Centre of Excellence in Theoretical Computer Science (ICE-TCS). For information about ICE-TCS and its activities, see

Moreover, she/he will visit Adrian Francalanza's group at the University of Malta during the project work and will benefit from the research experience on runtime verification within that group.

Qualification requirements

Applicants for the PhD fellowship should have an MSc degree in Computer Science, or closely related fields. Some background in concurrency theory and mathematical competence are desirable.

Applicants for the postdoctoral position should have, or be about to hold, a PhD degree in Computer Science or closely related fields. Previous knowledge of at least one of concurrency theory, process calculi, (structural) operational semantics and logic in computer science is highly desirable.

Remuneration
The PhD position provides a stipend of 290,000 ISK (roughly 2080 € at the current exchange rate) per month before taxes, for three years, starting as early as possible.

The wage for the postdoctoral position is 400,000 ISK (roughly 2870  € at the present exchange rate) per month before taxes. The position is for one year, starting on September 1, 2016 (later starting dates are possible), and is renewable for another year, based on good performance and mutual satisfaction.

Application details

Interested applicants should send their CV, including a list of publications, in PDF to all addresses below, together with a statement outlining their suitability for the project and the names of at least two referees.

Luca Aceto
email: luca@ru.is

Adrian Francalanza
email: adrian.francalanza@um.edu.mt

Anna Ingolfsdottir
email: annai@ru.is
We will start reviewing applications as soon as they arrive, and will continue to accept applications until the position is filled. However, we strongly encourage interested applicants to send in their applications as soon as possible.

Friday, June 03, 2016

10 funded positions for PhD studies in Computer Science at GSSI in L'Aquila

I have been asked to distribute this advertisement of ten fully-funded PhD positions at the Gran Sasso Science Institute, an international PhD school that is close to my heart and that is located in Abruzzo, my home region in Italy. I'd be grateful if you could distribute this announcement to potentially interested students. There are excellent opportunities for students interested in TCS.

The Gran Sasso Science Institute (GSSI - http://www.gssi.infn.it/ ), a recently established international PhD school and a Center 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 http://cs.gssi.infn.it/

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 use of the canteen;
-  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 http://www.gssi.it/phd/ and have to be accompanied by the curriculum vitae and by a statement letter describing:
 - a brief research project outlining the research challenges to consider for the PhD thesis;
 - the reasons for choosing GSSI for the PhD studies.

The deadline for application is: 1st September 2016 at 18.00 (Italian time zone).

For information see http://www.gssi.infn.it/phd/ or write an email to info@gssi.infn.it or call +39 0862 428026.

Wednesday, June 01, 2016

"Views on work in theoretical computer science" by Wolfgang Thomas


 
In the fifth installment of the series in which Fellows of the EATCS provide their advice to the budding TCS researcher, I am posting the contribution by Wolfgang Thomas. Happy reading!

As one of the EATCS fellows I have been asked to contribute some personal words of advice for younger people and on my research interests. Well, I try my best.

Regarding advice to a student and young researcher interested in TCS, I start with two short sentences:

  • Read the great masters (even when their h-index is low).
  • Don’t try to write ten times as many papers as a great master did.

And then I add some words on what influenced me when I started research - you may judge whether my own experiences that go back to „historical“ times would still help you.

By the way, advice from historical times, where blackboards and no projectors were used, posed in an entertaining but clearly wise way, is Gian-Carlo Rota’s paper „Ten Lessons I Wish I Had Been Taught“ (http://www.ams.org/notices/199701/comm-rota.pdf). This is a view of a mathematician but still worth reading and delightful for EATCS members. People like me (68 years old) are also addressed - in the last lesson „Be Prepared for Old Age“…

Back in the 1970’s when I started I wanted to do something relevant. For me this meant that there should be some deeper problems involved, and that the subject of study is of long-term interest. I was attracted by the works of Büchi and Rabin just because of this: That was demanding, and it treated structures that will be important also in hundred years: the natural numbers with successor, and the tree of all words (over some alphabet) with successor functions that represent the attachment of letters.

The next point is a variation of this. It is a motto I learnt from Büchi, and it is a warning not to join too small communities where the members just cite each other. In 1977, when he had seen my dissertation work, Büchi encouraged me to continue but also said: Beware of becoming member of an MAS, and he explained that this means „mutual admiration society“. I think that his advice was good.

I am also asked to say something about principles for the postdoctoral phase. It takes determination and devotion to enter it. I can say just two things, from my own experience as a young person and from later times. First, as it happens with many postdocs, in my case it was unclear up to the very last moment whether I would get a permanent position. In the end I was lucky. But it was a strain. I already prepared for a gymnasium teacher’s career. And when on a scientific party I spoke to Saharon Shelah (one of the giants of model theory) about my worries, he said „well, there is competition“. How true. So here I just say: Don’t give away your hopes - and good luck. - The other point is an observation from my time as a faculty member, and it means that good luck may be actively supported. When a position is open the people in the respective department do not just want a brilliant researcher and teacher but also a colleague. So it is an important advantage when one can prove that one has more than just one field where one can actively participate, that one can enter new topics (which anyway is necessary in a job which lasts for decades), and that one can cooperate (beyond an MAS). So for the postdoc phase this means to look for a balance between work on your own and work together with others, and if possible in different teams of cooperation.

Finally, a comment on a research topic that excites me at this moment. I find it interesting to extend more chapters of finite automata theory to the infinite. This has been done intensively in two ways already - we know automata with infinite „state space“ (e.g., pushdown automata where „states“ are combined from control states and stack contents), and we know automata over infinite words (infinite sequences of symbols from a finite alphabet). Presently I am interested in words (or trees or other objects) where the alphabet is infinite, for example where a letter is a natural number, and in general where the alphabet is given by an infinite model-theoretic structure. Infinite words over the alphabet N are well known in mathematics since hundred years (they are called points of the Baire space there). In computer science, one is interested in algorithmic results which have not been the focus in classical set theory and mathematics, so much is to be done here.

Tuesday, May 31, 2016

Scott Smolka's advice to the young theoretical computer scientist

As the fourth installment of the series in which Fellows of the EATCS provide their advice to the budding TCS researcher, I am posting the advice from Scott Smolka. Enjoy!

Advice I would give to a student interested in TCS Not surprising, it all starts with the basics: automata theory, formal languages, algorithms, complexity theory, programming languages and semantics.

Advice I would give a young researcher in TCS Go to conferences and establish connections with more established TCS researchers. Seek to work with them and see if you can arrange visits at their home institutions for a few months.

A short description of a research topic that excites me at this moment in time (and possibly why) Bird flocking and V-formation are topics I find very exciting. Previous approaches to this problem focused on models of dynamic behavior based on simple rules such as: Separation (avoid crowding neighbors), Alignment (steer towards average heading of neighbors), and Cohesion (steer towards average position of neighbors). My collaborators and I are instead treating this as a problem of Optimal Control, where the fitness function takes into account Velocity Matching (alignment), Upwash Benefit (birds in a flock moving into the upwash region of the bird(s) in front of them), and Clear View (birds in the flock having unobstructed views). What’s interesting about this problem is that it is inherently distributed in nature (a bird can only communicate with its nearest neighbors), and one can argue that our approach more closely mimics the neurological process birds use to achieve these formations.

Thursday, May 26, 2016

Sad news: Zoltán Ésik passed away yesterday

Our good colleague and friend Zoltán Ésik passed away suddenly yesterday afternoon in the hotel room where he was staying with his wife during a visit to our group at Reykjavik University. He had delivered a survey talk at Reykjavik University on the Equational Logic of Fixed Point Operations on Tuesday and we were making plans for the coming days.


Zoltán was a scientist of the highest calibre; he was one of the prime movers in the monumental development of Iteration Theories, amongst many other achievements. He had served the EATCS as a member of its Council for many years, had recently been named as one of the 2016 EATCS Fellows and he had been a member of the Presburger Award Committee for the last two years.

There is much more to be said about his scientific achievements and warm personality, but this will have to wait for better times.

R.I.P. Zoltán. 

Wednesday, May 25, 2016

Giuseppe Italiano's advice to young researchers in TCS

As the third installment of the series in which Fellows of the EATCS provide their advice to the budding TCS researcher, I am posting the advice from Giuseppe Italiano. Happy reading!

The advice I would give to a student interested in TCS There’s a great quote by Thomas Huxley: “Try to learn something about everything and everything about something.” When working through your PhD, you might end up focusing on a narrow topic so that you will fully understand it. That’s really great! But one of the wonderful things about Theoretical Computer Science is that you will still have the opportunity to learn the big picture!

The advice I would give a young researcher in TCS Keep working on the problems you love, but don’t be afraid to learn things outside of your own area. One good way to learn things outside your area is to attend talks (and even conferences) outside your research interests. You should always do that!

A short description of a research topic that excites me at this moment in time (and possibly why) I am really excited by recent results on conditional lower bounds, sparkled by the work of Virginia Vassilevska Williams et al. It is fascinating to see how a computational complexity conjecture such as SETH (Strong Exponential Time Hypothesis) had such an impact on the hardness results for many well-known basic problems. (Editor's notes: You might be interested in the slides for the presentations given at this workshop that was co-located with STOC 2015.)