Monday, September 17, 2012

[DMANET] Two RA positions

Royal Holloway, University of London
Department of Computer Science
Research Assistant - Two Posts

Salary is in the range £32,256 to £38,072 per annum inclusive of London

Many business processes (or workflows) can be modelled as a set of
computational tasks or steps. There will usually be some flexibility in the
order in which those steps may be completed, and restrictions on the users
who can perform each step. Whilst it is comparatively easy to ensure that
such policies are enforced, we may wish to impose more complex rules on the
business process. We might require, for example, that the same user does not
perform a particularly sensitive combination of steps. The Workflow
Satisfiability Problem (WSP) asks whether it is possible to allocate users
steps in such a way that all constraints are satisfied. For almost all types
of constraints of interest, WSP is NP-hard. Given that it is important to
know whether a workflow can be scheduled we require algorithms for the WSP
that run in a reasonable amount of time. The project will focus on designing
and implementing efficient algorithms for the WSP, focusing on techniques
from fixed-parameter algorithmics.

The successful candidates will work with Gregory Gutin, David Cohen and
Crampton developing,analysing and implementing such algorithms. Applicants
must have a background in a relevant mathematical discipline and have a
record of publishing original research at high quality venues. They must
good working knowledge of design and analysis of algorithms. They should
interest in information security. They should be happy to work independently
and as part of a team and be willing to attend international conferences,
meetings and workshops.

The first Research Assistant must have good working knowledge of
parameterized algorithmics. Basic knowledge of constraint satisfaction and
exponential algorithms is desirable.

The second Research Assistant must have significant experience in algorithms
engineering, and have interest in working on problems motivated by the
information security industry. Basic knowledge of constraint satisfaction
parameterized algorithms is desirable.

These are full time posts available from the 1st February 2013 or as soon as
possible thereafter for a fixed term period of three years. These posts are
based in Egham, Surrey in the United Kingdom.

For further details of these posts, please view and apply online at

* Contributions to be spread via DMANET are submitted to
* 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.