[DMANET] Two Research Positions in Algorithms and Complexity at the University of Oxford

Professor Leslie Ann Goldberg is looking for two postdoctoral researchers to join the ERC project "Mapping the Complexity of Counting" at the University of Oxford.

This is a five-year project from 1 Mar 2014 to 28 Feb 2019.
The positions are available for the duration of the project (subject to satisfactory performance).

The salary range is £29,541 - £36,298, depending on experience.

Deadline for applications: 15 November 2013

Details and application form at
https://www.recruit.ox.ac.uk/pls/hrisliverecruit/erq_jobspec_version_4.jobspec?p_id=110002

The overall objectives of the project are:

* 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).

* 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. The key problem domains that will be considered are graph homomorphism problems (including generalised weighted homomorphism problems), counting constraint satisfaction problems and holant problems. Key challenges include determining the effect of restrictions such as planarity, bipartiteness and bounded-degree constraints on the complexity of graph-theoretic counting problems.

Candidates should have a PhD in algorithms and complexity or in a closely related area of discrete mathematics. Expertise in one or more of the following would be helpful: combinatorics or discrete probability, graph polynomials or partition functions, mixing rates of Markov chains, constraint satisfaction problems including algebraic methods for classifying their difficulty, holographic algorithms or holant problems.



**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************