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