Skip to main content

EPSRC grant for Dave Cohen

  • Date12 March 2014

The grant is for research in Constraint Network Tractability: Beyond Structure and Language.


Constraint Satisfaction is a very general way of specifying feasibility questions: Scheduling, Machine Vision, Timetabling, Machine Allocation, Delivery Routing are all classic examples.
Such problems are computationally hard so a considerable effort has been invested into finding when particular classes may have practicable algorithms. This work has been successful but has concentrated so far on restricting the structure or language allowed when specifying instances.

In this work Professor Cohen will be working with Professor Cooper from the University of Toulouse, and Professor Jeavons and Dr Zivny from the University of Oxford, to find a unifying theory for the known tractability results. Their unique and ambitious contribution is to characterise tractable cases by forbidding small patterns which embody the reasons for hardness.

The hope is that the list of such forbidden patterns is amenable to a unifying theory. The team will be working on this research for three years.

Related topics

Explore Royal Holloway

Get help paying for your studies at Royal Holloway through a range of scholarships and bursaries.

There are lots of exciting ways to get involved at Royal Holloway. Discover new interests and enjoy existing ones

Heading to university is exciting. Finding the right place to live will get you off to a good start

Whether you need support with your health or practical advice on budgeting or finding part-time work, we can help

Discover more about our 21 departments and schools

Find out why Royal Holloway is in the top 25% of UK universities for research rated ‘world-leading’ or ‘internationally excellent’

Royal Holloway is a research intensive university and our academics collaborate across disciplines to achieve excellence.

Discover world-class research at Royal Holloway

Discover more about who we are today, and our vision for the future

Royal Holloway began as two pioneering colleges for the education of women in the 19th century, and their spirit lives on today

We’ve played a role in thousands of careers, some of them particularly remarkable

Find about our decision-making processes and the people who lead and manage Royal Holloway today