Friday, April 29, 2016

Best paper awards at ICALP 2016

The PCs for the three tracks of ICALP 2016 have selected the articles that will receive the best paper and best student paper awards at the conference.

The best paper awards will go to the following papers:
The following papers will receive the best student paper awards:
Congratulations to the authors of the award-receiving papers! 

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!