Skip to main content

Research Assistant on Mapping the Complexity of Counting

Posted: 19th June 2017

Department of Computer Science, Wolfson Building, Parks Road, Oxford.
Research Assistant on Mapping the Complexity of Counting

Fixed-term until 28 February 2019 (starting as soon as possible)
Grade 7: £31,076-£38,183pa

We are pleased to announce the availability for a full-time Research Assistant to work with Professor Leslie Ann Goldberg and her group on algorithms and complexity in connection with the ERC project "Mapping the Complexity of Counting (MCC)" until 28 February 2019 (starting as soon as possible).

As a researcher on this project, you will be expected to undertake the following objectives; to map out the landscape of computational counting problems (both exact and approximate), determining which problems are tractable, and which are intractable (quantifying the extent of tractability), and to discover complexity characterisations which elucidate the features that make counting problems tractable or intractable (telling us why each problem is tractable or intractable). Within the context of these overall objectives, the goal is to study classes of counting problems which are as wide as possible (obviously including the problems that arise in practice), and within these classes, to develop complexity dichotomies/characterisations which are as precise as possible.

You should have a PhD (or be near completion) and a first degree in Computer Science or a related mathematical discipline and a research record in algorithms and complexity or a related area. Postdoctoral experience and expertise in one or more of the following is desirable; combinatorics or discrete probability, graph polynomials or partition functions, mixing rates of Markov chains, constraint satisfaction problems including algebraic methods for classifying their difficulty and holographic algorithms or holant problems.

The closing date for applications is 12 noon on 19 July 2017. Interviews will be held on 2 August 2017 via Skype.

The post, which is a full time appointment, is funded by ERC. It has a salary on the University grade 07S scale (currently £31,076 to £38,183 p.a.). This includes membership of the Universities Superannuation Scheme (USS) and has an annual leave entitlement of 38 days per year (inclusive of all public holidays and university closed periods).

For further details and to apply please visit:

Committed to equality and valuing diversity