Monday, April 18, 2016

Accepted papers for ICALP 2016

The list of accepted papers for ICALP 2016 is out. The list of papers looks truly excellent to me and the conference programme will, as usual, give a broad snapshot of current research in TCS. I like to think that there will be something interesting for every TCS research in each track of the conference.

Thanks to the PCs for the three tracks for their sterling work and to Michael Mitzenmacher, Yuval Rabani and Davide Sangiorgi for their leadership as PC chairs.

I hope to see many of you in Rome for the conference. 

Wednesday, April 13, 2016

Yuval Rabani, the PC chair for the Track A of ICALP 2016, has written  the first of a short series of posts on tumblr on the work of the PC for Track A. Further posts will follow on his blog, which is devoted solely to ICALP 2016. 

Quoting from Yuval's post: 
I’d like to encourage all theoreticians to attend ICALP 2016 in Rome. Rome has art. Rome has history. Rome has art history. Rome has fashion. Rome has design. Rome has espresso, Rome has gelato. Rome has tomatoes. Rome has porcini mushrooms. Rome even has jazz clubs (not to mention opera). Best of all, the program committee worked very hard to produce an excuse to charge your grants for the trip!
Many thanks to Yuval and his PC for their splendid work!

Let me close by adding that Roma also has Casa del Jazz :-)

Addendum: Yuval's second post is available here.

Thursday, March 24, 2016

Mark Braverman (Princeton University) receives the EATCS Presburger Award 2016

The European Association for Theoretical Computer Science (EATCS) has awarded the 2016 Presburger Award to Mark Braverman (Princeton University, USA). Congratulations to Mark!

Mark Braverman has achieved fundamental results in complexity theory, the theory of computation over the reals, approximation algorithms, computational learning theory, information theory, algorithmic economics, pseudorandomness and communication complexity. In 2009, using a surprisingly simple argument from harmonic analysis, he completely settled the Linial-Nisan conjecture that any k-wise independent distribution will look completely random to a bounded depth boolean circuit. He and his collaborators cast new light on the computability and computational complexity of Julia sets and disproved a long-standing conjecture of Krivine on the value of Grothendieck’s constant. Through his many seminal results, he has become a leader in extending information theory to an interactive setting, developing the theory of information complexity, a thriving subfield at the boundary of theoretical computer science and electrical engineering. On this topic, he is currently co-organizing a semester on the Nexus of Information and Computation Theories at the Institut Henri Poincaré in Paris, January-April 2016. For more information see here.

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

The Presburger Award carries a prize money of 1000 Euros  and will be delivered at ICALP 2016, which will take place in Rome (Italy) from the 12th till the 15th of July 2016.

The 2016 Presburger Award Committee consisted of Zoltan Esik (University of Szeged, Hungary), Marta Kwiatkowska (University of Oxford, UK) and  Claire Mathieu (ENS Paris, France; chair).

Friday, March 11, 2016

Looking for input on promoting PhD education and research in TCS

As current president of the EATCS, I am very interested in hearing the opinion of PhD students and young researchers in TCS on what an association like the EATCS could do to promote PhD education and research in the field, and to entice young scientists to carry out research in TCS. (Of course, the opinion of every TCS researcher is welcome!) For instance, should we increase the offer of our EATCS Young Researcher Schools?

Please post your suggestions as comments to this post. I'll collect all your suggestions and discuss them with the Council of the EATCS.

Thanks in advance for your input! The EATCS is here to serve the whole of the TCS community and we will consider all your opinions carefully.

Tuesday, March 08, 2016

We are hiring at long last!

Al long last, we have advertised several faculty positions in the School of Computer Science at Reykjavik University! The call is available here, but I also copy-paste it below  for ease of reference. (If following that link shows a page that is encrypted in Icelandic, change to English using the flag at the top corner on the right-hand side.) (I fixed the URL so that it always redirects to the English page.)

Note that strong applicants in TCS are encouraged to apply, even though the call mentions other areas explicitly. One position is earmarked for Software Engineering, which does not rule out some TCS-related research.

Information about research and faculty in our school is here.


The School of Computer Science at Reykjavik University invites applications for several full-time faculty positions.

We are looking for energetic, highly qualified academics who, apart from developing their own research programs, will strengthen some of the existing research areas within the School, or build bridges between them or with industry. Of particular interest are candidates in the areas of software engineering, data analytics, computer security and systems, broadly construed, but exceptionally qualified candidates from all areas of computer science are encouraged to apply.

Candidates are expected to have a proven international research record and will be expected to play a full part in the teaching and administrative activities of the School. The applicants are expected to teach courses at both graduate and undergraduate level. It is preferred that applicants have a demonstrated history of excellence in teaching at the graduate and undergraduate levels. A PhD in computer science or closely related field is required.

Salary and rank are commensurate with experience. The positions are open until filled, with the earliest available starting date in August 2016, but later starting dates can be negotiated.

The review of the applications will begin on March 15th and continue until the positions are filled. Application letters should be submitted through the University's online application submission system here below.
  • a cover letter
  • a CV with a list of publications,
  • a research statement,
  • copies of three to five major publications,
  • a teaching statement,
  • supporting material regarding excellence in teaching, and
  • any other relevant information the applicant wishes to supply.

Please arrange to have at least three letters of recommendation sent directly to (subject "Faculty Positions in CS") with a cc to the Dean of the School of Computer Science, DrProf. Yngvi Björnsson ( Informal communication and discussions on any aspect related to the positions are encouraged, and interested candidates are welcome to contact the chairman of the search committee, DrProf. Magnús Már Halldórsson (, for further information.

The School of Computer Science at Reykjavik University has about 800 students and 18 permanent faculty members. The school offers undergraduate and graduate programs in computer science and software engineering, as well as a combined-degree undergraduate program in discrete mathematics and computer science. The doctoral program within the School received its ministerial accreditation in 2009. Quoting from the accreditation report on PhD studies from 2009 (
The School of Computer Science is "the strongest in Iceland" (p. 6) and its research is "on a similar level to that of cutting-edge institutions worldwide" (p. 15).

For further information about the School of Computer Science at Reykjavik University and its activities, see

Monday, February 22, 2016

February 2016 issue of the Bulletin of the EATCS

I am happy to inform you that the 118th issue of the EATCS Bulletin is now available online at, featuring, amongst others:

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

You can download a pdf with the printed version of the bulletin from
Many thanks to the column editors, the authors of the contributions, Kazuo Iwama, the editor in chief of the BEATCS, and Efi Chita at the EATCS Secretary Office for the enormous work they have put into producing this issue of the Bulletin. 

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

Wednesday, February 17, 2016

EATCS Fellows class of 2016 named

The EATCS has recognized five of its members for their outstanding contributions to theoretical computer science by naming them as recipients of an EATCS fellowship. The EATCS Fellows for 2016 are:
  • Zoltán Ésik (University of Szeged, Hungary; for "contributions to the fields of automata and formal languages, iteration theories, algebra and logic in computer science, and in particular to their connections. He has been able to apply deep theorems of some area to problems of other fields, yielding particularly short, beautiful and mathematically concise proofs."
  • David Harel (Weizmann Institute of Science, Israel; for "fundamental contributions to program verification, database theory, and software engineering, as well as for exceptional merits as a writer and teacher. The Statecharts model has had profound impact on software and systems engineering."
  • Giuseppe F. Italiano (University of Rome Tor Vergata, Italy; for "fundamental contributions to the design and analysis of algorithms for solving theoretical and applied problems in graphs and massive data sets, and for his role in establishing the field of algorithm engineering."
  • Kurt Mehlhorn (Max-Planck-Institut für Informatik, Germany; for "his influential contribution to the whole field of algorithmics over the past decades. In addition to key theoretical contributions, he has brought basic research closer to practice."
  • Scott A. Smolka (Stony Brook University, USA; for "fundamental contributions to process algebra, model checking, probabilistic processes, runtime verification, and more recently for the successful application of most of these theories to cardiac-cell modelling and analysis."
The aforementioned members of the EATCS were selected by the EATCS Fellow Selection Committee, after examining the nominations received from our research community. The EATCS Fellow Selection Committee for 2016 consisted of
  • Rocco De Nicola (IMT Lucca, Italy; chair),
  • Paul Goldberg (Oxford, UK),
  • Anca Muscholl (Bordeaux, France),
  • Dorothea Wagner (Karlsruhe, Germany) and
  • Roger Wattenhofer (ETH Zurich, CH).
The EATCS Fellows Program was established by the association  in 2014 to recognize outstanding EATCS members for their scientific achievements in the field of Theoretical Computer Science.

The EATCS is very proud to have the above-mentioned members of the association among its fellows.

The list of EATCS Fellows is available at