Ode to the Automata Tutor

I am slowly emerging from teaching a first year course on topics in Discrete Mathematics to about 250 students at Reykjavik University. (I have one more lecture to deliver after Easter and then the not-so-small matter of over 200 exam papers to grade :-() This is the second discrete mathematics course the students take and it is the second spring semester in a row that I teach it.

As part of the course, I am supposed to cover  the basics of grammars, finite automata and regular expressions. This is a first year course, so I do not cover much of the theory related to these formalisms and their connections. Mostly I expect the students to be able to design grammars, finite automata and regular expressions for some relatively simple languages.

In both editions of my course, which has been followed by about 500 students overall, I have used the AutomataTutor to support my teaching of material related to finite automata and to grade student assignments automatically.

For what it is worth, I strongly encourage my readers to try the tool and to use it in their undergraduate courses. In my experience, the students love to learn DFA and NFA programming using the Automata Tutor and to work on assignments that employ it. The automatic feedback and grading provided by the Automata Tutor are almost magical. (See this paper for a description of how the tool does both.) This is how the construction of finite automata that recognize regular languages should be taught in a modern way! I wish I had similar tools for all the topics I need to cover in that course.

From my perspective (and from that of my TAs), automatic grading is a real bonus. I love to teach, but I really hate to grade a large number of student assignments. Students can be very creative in their solutions and grading them is a very time consuming, haphazard and inconsistent process for any human. The algorithms embodied in the Automata Tutor produce consistent results at the press of a button and the students receive a grade straight away as well as excellent hints on how to improve incorrect solutions.

Thanks to Rajeev Alur, Loris D'Antoni, Sumit Gulwani, Dileep Kini, Mahesh Viswanathan and their co-workers, teaching basic finite-automata theory to hordes of first-year students can now (largely :-)) be done without tears. To boot, the folks at Automata Tutor have always been ready to provide technical help, when that was needed.

I'll keep using the Automata Tutor in my courses and I hope that you will do so too. That is the best way to thank our colleagues for the work they have done and are still doing on that tool.

February 2015 issue of the Bulletin of the EATCS on line

Thanks to the work of Kazuo Iwama, editor in chief of the bulletin, and of his collaborators, the February 2015 issue of the Bulletin of the EATCS is now available on line. You can download the whole issue in PDF from here, if you prefer. As a service to the TCS community, the bulletin continues being open access because of the support of the members of the EATCS, whom I thank wholeheartedly.

Amongst other things, this issue contains contributions by David Eppstein on K-Best Enumeration, Vikraman Arvind on Robust Oracle Machines revisited, Gaudi Taubenfeld on A Closer Look at Concurrent Data Structures and Algorithms (pages 59-82 of the whole issue), Jukka Suomela on Local Coordination and Symmetry Breaking ((pages 83-110 of the whole issue), Andreas Blass on Negative Probability and by Juraj Hromkovic who kicks off the new-look Education Column with a piece entitled Homo Informaticus.

I welcome Stefan Schmid as new editor of the Distributed Computing Column and thank Panagiota Fatourou for her sterling editorial work over many years.

Enjoy it. 

Video made by the female CS student association at Reykjavik University

I learnt a few things about some of the students taking the first-year course I am teaching right now by watching this well-made video.

EATCS Fellows class of 2015 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 2015 are:

• Artur Czumaj (University of Warwick, United Kingdom) for "contributions to analysis and design of algorithms, especially to understanding the role of randomization in computer science";
• Mariangiola Dezani-Ciancaglini (Università di Torino, Italy) for "distinguished and seminal achievements in formal methods and foundations of programming languages, introducing or developing new type systems for the lambda-calculus as well as for the pi-calculus and related calculi";
• Thomas A. Henzinger (Institute of Science and Technology Austria) for "fundamental contributions to formal verification and synthesis of computer and biological systems";
• Dexter Kozen (Cornell University, USA) for "pioneering and seminal work in fields as diverse as  complexity theory, logics of programs, algebra, computer algebra and probabilistic semantics";
• Moshe Y. Vardi (Rice University, USA) for "fundamental and lasting contributions to the development of logic in computer science and exceptional services to the community of theoretical computer science."

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

• Rocco De Nicola (IMT Lucca, Italy),
• Paul Goldberg (Oxford, UK),
• Anca Muscholl (Bordeaux, France),
• Dorothea Wagner (Karlsruhe, Germany; chair) 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 organization among its fellows.

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

Presburger Award 2015 to Xi Chen (Columbia University)

The European Association for Theoretical Computer Science (EATCS) has awarded the 2015 Presburger Award to  Xi Chen (Columbia University, New York, USA). Congratulations to Chen!

Xi Chen, born in 1982, has made fundamental contributions in a variety of areas within theoretical computer science. His work in algorithmic game theory and computational economics includes the answer to the long standing question about the computational complexity of Nash equilibria for two-player games, showing PPAD-completeness. For classes of markets and types of utility functions widely used in economics, he settled the complexity of market equilibria, again showing PPAD-completeness. His work on complexity theory includes a complete dichotomy theorem for partition function computation, showing it to be either polynomial or #P-complete, as well as for counting constraint satisfaction problems with complex weights, general concepts that include e.g. counting graph homomorphisms. His work on algorithms includes a proof that isomorphism of strongly regular graphs, a well-known hard case for the graph isomorphism problem, can be tested in time exponential in n^1/5 - the first significant progress in more than a decade.

The  Presburger Award is given 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 list of the previous recipients of the Presburger Award is available at

http://eatcs.org/index.php/presburger

The Presburger Award carries a prize money of 1000 Euros and will be delivered at ICALP 2015, which will take place in Kyoto (Japan) from the 6th till the 10th of July 2015 in co-location with LICS 2015.

The 2015 Presburger Award Committee consisted of Zoltan Esik (University of Szeged, Hungary), Claire Mathieu (ENS Paris, France) and Peter Widmayer (ETH Zurich, CH; chair).

Research Positions in Algorithms and Networks at Reykjavik University

Applications are invited for two research positions at the School of Computer Science (SCS), Reykjavik University, funded by a grant from the Icelandic Research Fund, under the direction of Prof. Magnus M. Halldorsson.  The positions can be either at any level: Ph.D. student, post-doctoral, or at faculty level. The application deadline is March 15, 2015.

The foci of the research group can be divided into three interrelated areas: algorithms for wireless networks; distributed graph algorithms; and approximation algorithms on graphs and networks.

Applicants should have a strong research profile (or potential) and a solid background in the analysis of algorithms. A general understanding of networking and/or distributed computing is expected. Self-motivation, open mind and team spirit are all helpful ingredients.

For more information and application procedures, see full announcement at
http://www.ru.is/~mmh/jobs-feb2015.htm
For informal inquires, contact Magnus M. Halldorsson, mmh@ru.is.

Call for Nominations: EiC for ACM Transactions on Computational Logic

Call for Nominations
Editor-In-Chief
ACM Transactions on Computational Logic

The term of the current Editor-in-Chief (EiC) of the journal ACM Transactions on Computational Logic (TOCL) is coming to an end, and the ACM Publications Board has set up a nominating committee to assist the Board in selecting the next EiC. TOCL was established in 2000 and has been experiencing steady growth, with 74 submissions received in 2014.

Nominations, including self nominations, are invited for a three-year term as TOCL EiC, beginning on July 1, 2015. The EiC appointment may be renewed at most once. This is an entirely voluntary position, but ACM will provide appropriate administrative support.

For further details, see

http://tocl.acm.org/announcements/Call-for-Nominations.pdf

EATCS Award 2015 to Christos Papadimitriou

I am pleased to announce that the EATCS Awards Committee consisting of Fedor Fomin, Kim G. Larsen and Vladimiro Sassone (chair) has selected  Christos Papadimitriou (UC Berkeley, USA; WWW: http://www.cs.berkeley.edu/~christos/; Wikipedia: http://en.wikipedia.org/wiki/Christos_Papadimitriou) as the recipient of the EATCS Award 2015. Congratulations to Christos!

The award, which is given to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career, will be presented to Christos at ICALP 2015, which will be held in Kyoto, Japan, in the period 6-10 July 2015. The list of previous recipients of the EATCS Award is here. An official laudatio for the award is forthcoming. What follows is a short preliminary laudatio penned for this blog post.

Christos Papadimitriou’s body of work is of amazing breadth and depth, and has had a profound and lasting influence on many areas of Computer Science.

In an era of great specialization, Christos Papadimitriou stands out as a present-day Renaissance man. He is an intellectual who, citing the title of one of his essays, is not afraid of asking "big queries" and  applies the “computational lens” to shed light on important problems in several areas of scientific enquiry, ranging from economics to the theory of evolution. While doing what he might himself call “extroverted Computer Science”, he has contributed truly seminal work to a large number of fields within our subject, including algorithmics, complexity theory, computational game theory, database theory, internet and sensor nets, optimization and robotics.

Christos Papadimitriou is also one of the very best expositors and teachers within our field. He has written classic textbooks on the theory of computation, combinatorial optimization, database concurrency control, computational complexity and algorithms. In so doing, he has helped to inspire several generations of computer scientists.

If that wasn't enough, Christos Papadimitriou is a tireless expositor and is able to explain the beauty of our discipline to a general educated public. He is not afraid to cross boundaries, and to use literary forms such as novels (see "Turing: A Novel About Computation", http://mitpress.mit.edu/books/turing-novel-about-computation) and comics (see the graphic novel "Logicomix", http://en.wikipedia.org/wiki/Logicomix) to offer accessible expositions of the science of computing and its origins.

To sum up, Christos Papadimitriou is one of those rare scientists who combines a large, influential and varied body of scientific results with the gifts of an inspiring teacher and of a great communicator.

Associate/Full Professor Position at Oxford in Algotithms or Complexity

The Department of Computer Science at the University of Oxford is planning to make an appointment at associate/full professor level with effect from 1 September 2015 or as soon as possible thereafter. Applicants should hold a PhD in computer science or a related subject and have experience in any area related to algorithms or complexity.  

The details are here. 

Please help spread the word.

Three postdoc positions in Computer Science at the Gran Sasso Science Institute, L'Aquila

I  have been asked to advertise three postdoc positions in Computer Science that are available at the Gran Sasso Science Institute in L'Aquila, Italy. The  deadline for application is the 2nd of February. I trust that these positions might be of interest to some of the readers of this blog. 

The Gran Sasso Science Institute currently hosts a little under 20 PhD students in Computer Science and there will be about ten more joining the institute in November 2015. The PhD students from there with whom I have had the pleasure to interact are highly motivated and have good potential. The successful applicants will have a good chance to get some of them involved in their own research. 

L'Aquila lies in my home region, Abruzzo, and  is surrounded by beautiful mountains, national parks and many historical sites. 

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 12 postdoctoral research positions. Three of these positions are dedicated to Computer Science and more specifically to themes that are strongly connected to the pillars of the PhD program in Computer Science (http://cs.gssi.infn.it), namely:

 * Foundations of social and computer networks
 * Software systems and services
 * Specifications and analysis of concurrent reactive systems

Apart from pursuing their own research agenda, the successful candidates will have the opportunity to take part in the supervision of the roughly 20 PhD students in Computer Science and to cooperate with members of the research group and of the Scientific Board (http://cs.gssi.infn.it/phd-program/information/), as well as with the frequent guests of the institute.

The deadline for application is:

*February 2, 2015 at 6:00 pm (Rome time)*

The annual gross salary is EURO 40K and lunch tickets are provided for working days. The positions are for two years. Candidates must have earned their doctoral degree not earlier than  January 1, 2008.

Selected candidates are expected to start their appointments not later than *September**1st, 2015. *

For information see http://www.gssi.infn.it/postdoc/ and http://www.gssi.infn.it/postdoc//doc01856420141216105324.pdf

.

For any further information feel free to contact Rocco De Nicola (rocco.denicola@imtlucca.it rocco.denicola@imtlucca.it

>), the coordinator of the PhD program in Computer Science, or any other member of the research group or of the Scientific Board http://cs.gssi.infn.it/phd-program/information/

ACM Fellows 2014

The ACM Fellows vintage 2014 have been named. The list includes several colleagues whose work has advanced TCS, including Samson Abramsky (who is recognized for his contributions to domains in logical form, game semantics, categorical quantum mechanics, and contextual semantics),  Leslie Lamport (who received the Turing Award before being named ACM Fellow), Michael Mitzenmacher and Omer Reingold amongst many others. Congratulations to all the ACM Fellows!

As a fellow Italian academic working abroad,  I am happy to see Alberto Sangiovanni Vincentelli honoured for his contributions to electronic design automation.

PC chairs for ICALP 2016

I am happy to inform you that the PC chairs for ICALP 2016 will be

• Track A: Yuval Rabani (Hebrew University Jerusalem, Israel)
• Track B: Davide Sangiorgi (University of Bologna, Italy)
• Track C: Michael Mitzenmacher (Harvard University, USA)

Many thanks to these colleagues for their willingness to serve as PC chairs for the conference, which will be held in Rome.

REMINDER: The deadline for nominations for several EATCS Awards is approaching!

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

• 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, 2015.

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

A neat problem from the 1989 Maths Olympiads

A few days ago, Universidad Complutense de Madrid hosted a celebration of the 50th anniversary of the Spanish Maths Olympiads. The programme involved three talks. The first was on "other number systems" (quaternions and octonions) and the second dealt with the roots of random polynomials. In the third talk,  Vicente Muñoz Velázquez presented his personal views on the nature of mathematics before discussing some of the highlights of his research area leading to Yang-Mills and Mass Gap.

According to Vicente, mathematics is a human product and its characteristics are:

• (The rules of) Logic, 
• (Modelling of) Reality, 
• Beauty (transversality, relations between apparently distant fields, generalization and abstraction), 
• Social activity,
• Applicability. 

I could not help but think that those characteristics apply equally well to computer science, with the added twist that computer scientists are not only modelling reality, but also inventing and breathing life into "new realities".

During his talk, Vicente presented a problem from the 1989 International Maths Olympiad, in which he took part.

The problem was:

Prove that for each positive integer n there exist n consecutive positive integers none of which is a prime or a prime power.

This is a neat problem that perhaps some of you might like to try and solve.

EATCS Fellows 2015: Call for Nominations

In case you have not seen it before, here is the call for nominations for EATCS Fellows 2015.  Do nominate strong candidates for this accolade!

CALL FOR NOMINATIONS FOR EATCS FELLOWS 2015
                                                                              
                                             
INSTRUCTIONS:
Please note: all nominees and nominators must be EATCS Members

Submit by December 31 of the current year for Fellow consideration by
email to the EATCS Secretary (secretary@eatcs.org). The subject line
of the email should read "EATCS Fellow Nomination - ".

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) 
- Paul Goldberg (Oxford, UK)
- Anca Muscholl (Bordeaux, France)
- Dorothea Wagner (Karlsruhe, Germany, chair)
- 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 2015 must be received by December 31, 2014.

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)

October 2014 issue of the Bulletin of the EATCS

The October issue of the EATCS Bulletin is now available online at http://bulletin.eatcs.org/index.php/beatcs/issue/view/16 from where you can access the individual contributions separately.

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

The Bulletin of the EATCS is open access, so people who are not members of the EATCS can read it. Let me thank the members of the association who make this service of the community possible with their support.  (EATCS members have access to the member area, which contains news and related articles and provides access to the Springer Reading Room. Young researchers can find announcements of open positions, news and related articles.)

This issue of the bulletin is brimming with interesting content, with five EATCS Columns and a piece by David Woodruff surveying the work for which he had received the EATCS Presburger Award 2014 amongst others. You might also enjoy reading the transcript of a dialogue between Christian Calude and Kurt Mehlhorn about theory, LEDA and Algorithm Engineering. I find it inspiring to read Christian's dialogues with famous members of our community and I always learn something useful from them. (Unfortunately, the lessons I think I learn do not make it often into my work practices. That's the theory-practice divide, I guess :-))

Here are a couple of excerpts to whet your appetite.

• Kurt's motto, even definition, for Algorithm Engineering is: "Treat programs as first class citizens in algorithms research and not as an afterthought." He also adds that "Algorithm engineering is not only a sub-discipline of algorithms research. More importantly, it is a mind set."
• CC: How do you manage to juggle between so many jobs in di fferent countries?
  KM: I try to follow some simple principles.
  I avoid multi-tasking. I set aside time for particular tasks and then concentrate on them. For example, when I was writing my 1984 books and the LEDA book, I would work on the book every work day from 8:00 am to 12:00 pm. I would not accept phone calls or interruptions by students during this time. Now, the 8am to 12pm slot is reserved for reading, thinking and writing. The no-interruption rule still holds.
  I clean my desk completely every evening when I leave my o ffice, so that I can start with an empty desk the next morning.
  When I accept a new responsibility, I decide, what I am going to give up for
  it. For example, when I became vice-president of the Max Planck Society in 2002 (for a 6 year term), I resigned as editor of Algorithmica, Information and Computation, SIAM Journal of Computing, Journal of Discrete and Computational Geometry, International Journal of Computational Geometry and Applications, and Computing.
  And most importantly, I am supported by many people in what I do, in particular, my co-workers, my students, and then administrative staff in the institute and the department. Cooperation and delegation are very important.

Enjoy the issue and consider contributing to future ones!

First CFP for ICALP 2015

The first call for papers for ICALP 2015, which will be held in Kyoto in the period 6-10 July 2015, is available here.

I hope that you will consider submitting your best work to the conference. The event will be rich of scientific events and will be co-located with LICS 2015. To whet your appetite, here is the list of invited speakers and invited tutorials:

Invited Speakers

Ken Kawarabayashi, NII, Japan
Valerie King, University of Victoria, Canada
Thomas Moscibroda, MSR Asia, China
Anca Muscholl, University of Bordeaux, France (Joint with LICS)
Peter O'Hearn, Facebook, UK (Joint with LICS)

Invited Tutorial Speakers (Joint with LICS) 

Piotr Indyk, MIT, USA
Andrew Pitts, University of Cambridge, UK
Geoffrey Smith, Florida International University, USA

Masterclass speaker 

Ryuhei Uehara, JAIST, Japan

CFP for CCC'15 posted

Dieter van Melkebeek has informed me that the CFP for CCC'15 has just been posted. The direct link is http://computationalcomplexity.org/Archive/2015/cfp.html.

The deadline for submissions is November 26, 2014.

I hope that members of the CCC community will submit some of their best work to the first edition of the conference with open-access proceedings published in LIPIcs. 

Call for nominations: EATCS Award 2015

Please consider nominating outstanding theoretical computer scientists for the EATCS Award 2015. 

 

The EATCS Award 2015

Call for Nominations

Deadline: December 31st, 2014

The European Association for Theoretical Computer Science (EATCS) annually honours a respected scientist from our community with the prestigious EATCS Distinguished Achievement Award. The award is given
to acknowledge extensive and widely recognized contributions to theoretical computer science over a life long scientific career.  For the EATCS Award 2015, candidates may be nominated to the Award Committee consisting of

• Fedor Fomin (University of Bergen),
• Kim Guldstrand Larsen (Aalborg University) and 
• Vladimiro Sassone (University of Southampton).

Nominations will be kept strictly confidential. They should include supporting justification and be sent by e-mail to the chair of the EATCS Award Committee:

Vladimiro Sassone
Email: vsassone@soton.ac.uk

The list of previous recipients of the EATCS Award is at

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

The next award will be presented during ICALP 2015 in Kyoto, Japan.

Letter from the President of the EATCS for the October issue of the Bulletin

In case any of my two readers is interested in having a look, here is the letter from the president that will appear in the October issue of the Bulletin of the EATCS.

Dear colleagues,

First of all, I hope that you had a good summer break and that you have recharged your batteries for whatever challenges await you in the new academic year.

For many of us, the start of each academic year is accompanied by teaching courses to new cohorts of students. Computer Science enrollments seem to be increasing all over the world and several institutions, including mine, will have to decide how to handle the large number of students who are eager to enter our degree courses. I encourage you to have a look at the slides available here for an American perspective on computer science enrollments. Look also at this Harvard Crimson article. Course CS 50 at Harvard has over 800 undergraduates (and over 850 total) signed up, making it now the largest class at Harvard.

Having many students is, of course, a substantial amount of work, but the popularity of computer science also gives us a very good opportunity to entice  some of these students to study the theory of computing; let's make the most of it!

I enjoyed meeting several of you at ICALP 2014 in Copenhagen. It was a pleasure to see many young researchers and students at the conference, and I really appreciated the good attendance we had at the event. Thanks to all of you who made the trip to Copenhagen!

The 41st ICALP was an excellent conference, both scientifically and socially. The organizers did their very best to make it a memorable event, and I like to think that all the participants felt welcome and enjoyed the conference. On behalf of the EATCS, I warmly thank Thore Husfeldt and his team for doing an outstanding job.

You can read my report on ICALP 2014 in this issue of the Bulletin. The recordings of the invited talks and of the award session are available from the conference web page. I hope that you will watch them.

ICALP 2015 will be held in Kyoto, Japan, and will be co-located with LICS 2015. Kazuo Iwama is the ICALP 2015 general chair. After 42 years, this will be the first ever ICALP outside Europe and I am very excited at the prospect of holding ICALP in Japan. I hope that you will make plans to submit your best papers to the conference. The call for papers for the conference will be ready for distribution soon.

The general assembly of the EATCS decided that ICALP 2016 will be held in Rome, Italy. I thank Tiziana Calamoneri and her collaborators for their willingness to host us in Rome.

One of the important decisions that the Council of the EATCS will have to make over the next few months is related to the future publication outlet for the proceedings of ICALP from 2016. Our current contract with Springer will expire at the end of 2015, but we only have until March 2015 to negotiate any changes to it or to decide whether to move to a different publication outlet. I look forward to hearing any opinion you might have on this matter.

Regarding publications, I strongly encourage all the members of the EATCS to make all their publications freely accessible on line. It is our duty, as well as being in the interests of our science and in our own interest, to make access to our scientific work free of financial barriers for any researcher. This is possible even for papers that have appeared in journals and conference proceedings published by commercial publishers.

As usual at this time of the year, the EATCS issues calls for nominations for the EATCS Award, EATCS Fellows and the Presburger Award. (The call for the Gödel Prize will be published at a later time, when ACM SIGACT has named its representatives in the prize committee.) You can read the calls in this issue of the Bulletin; they have also been posted on mailing lists, blogs and social networks. Please distribute the calls as you see fit. Most importantly, I hope that you will take the time to nominate excellent researchers and papers for these awards. Awards and prizes are a way to recognize the achievement of some of our many outstanding colleagues and they put our favourite research fields in the spotlight. Last, but by no means least, awards provide examples and inspiration for the younger generations of researchers who are the future of our field as a whole. Writing a nomination takes some of our precious time, but it is worth it.

At the time of writing, the EATCS is cooperating with the newly formed ACM SIGLOG, the EACSL and the Kurt Gödel Society on a new award, which we hope to be in a position to announce in the not-too-distant future. I am also happy to announce that the Computational Complexity Conference will be held in cooperation with the EATCS from 2015.

On Thursday, 2 October, I attended a talk given at my university by Donald Sadoway, John F. Elliott Professor of Materials Chemistry at the Massachusetts Institute of Technology. His talk was inspirational and stressed the importance of research carried out at universities the world over. University research is even more fundamental today than it ever was because, according to Sadoway, universities are the places where truly innovative research takes place. In his view, corporate research laboratories do not embark in fundamental research today as they did in the past.

While listening to Sadoway's talk, I could not help but think about the sudden closure of Microsoft Research Silicon Valley. As you all know, Microsoft Research Silicon Valley had achieved a very high reputation within the theoretical-computer-science community because of the scientific standing of its stellar staff, the high impact of the work done at the laboratory, the mentoring role its members played within our research community (with many outstanding
young researchers spending important formative periods at the laboratory) and its stimulating research environment with frequent visits by high-profile scientists.

As the blog posts from TCS researchers and the associated comments clearly
indicate, losing Microsoft Research Silicon Valley has left our community with a sense of loss and sadness, also because of the timing and the abrupt nature of its closing.

With a laboratory like Microsoft Research Silicon Valley, Microsoft had gained a substantial amount of credence within the theoretical-computer-science community and had attracted some of the best talent in our field worldwide. Many outstanding young researchers had considered a position at Microsoft Research Silicon Valley and Microsoft's other research labs as their first choice, even above tenure-track or tenured positions at prestigious academic institutions. All this is now probably bound to change, which would be a loss for both Microsoft and our research community.

For what it is worth, I hope that Microsoft Research will continue to support research in theoretical computer science. Advances in the theory of computing will benefit the company in the long run and further investments by Microsoft in TCS will be beneficial for our field of study.

I thank you for reading this letter, and look forward to hearing suggestions and opinions from the members of the EATCS (and the community at large). You are the heart and soul of our association!