ACiD, Algorithms and Complexity in Durham, is a world-leading research group and one of the largest UK groups working in this area with research programmes involving many international collaborators. Theoretical Computer Science comprises the development of algorithmic techniques that efficiently exploit the power of modern computers, the study of the limits of computation and the ways in which we can cope with, and take advantage of, intractability, and the science of the unsolvable.
The group is broad-based with differing research foci within the general area of algorithms and complexity including computational complexity, proof complexity, descriptive complexity, (algorithmic) graph theory, exact algorithms, randomised algorithms, approximation algorithms, finite model theory, constraint satisfaction, interconnection networks, universal algebra and mathematical logic.
Lecturer and Postdoc Vacancies The School is seeking to recruit two Lecturers or Senior Lecturers in Computing Science. The closing date is 27 May 2013; details here. There is a vacancy for a Research Associate on the project Topology, geometry and Laplacians of simplicial complexes. The deadline for making applications is 28 May; details. And there is a deadline of 2 June for applications for the position of Research Associate on the project Detecting induced graph patterns; more information. Finally the School is recruiting a Research Associate to work in the Institute of Advanced Research Computing, a new pan-University inter-disciplinary research centre. The deadline is 27 May; details.
Opportunities for Research Students If you are interested in beginning a PhD or MSc by Research in October 2013, please email us (or consult a member of the group who you would like to work with). If you are a UK student who expects to graduate with a First, there are good opportunities for funding.
Best of 2012 Andrei Krokhin (and co-authors Laszlo Egri, Benoit Larose and Pascal Tesson) has been cited in Computer Reviews' Notable Computing Books and Articles of 2012 for the paper The Complexity of the List Homomorphism Problem for Graphs.
Congratulations to Aidan Chalk on the award of MSc (Research) for his work on bee colony optimization problems.
Research Grant Norbert Peyerimhoff and Stefan Dantchev (with colleagues Ioannis Ivrissimtzis and Alina Vdovina (Newcastle)) have obtained funding from EPSRC for their project Topology, Geometry and Laplacians of Simplicial Complexes.
Congratulations to James Gate and Jian Song on successful PhD vivas.
EPSRC Funding Daniel Paulusma and Iain Stewart have been awarded a grant for their project Detecting Induced Graph Patterns.
IAS Seminars The Institute of Advanced Study's thematic activity Times as Misty Window is a series of seminars on the use of phylogenetic methods.
Congratulations to Jeremy Kemp on the award of MSc (Research) for his thesis on All-Pairs Shortest Path Algorithms Using CUDA.
Graph Theory Our colleagues in Maths are organizing Graph Theory and Interactions in July 2013 as part of the LMS Durham Research Symposia.
Dagstuhl Seminar Andrei Krokhin is organizing a week long seminar on The Constraint Satisfaction Problem.
Welcome October 2012: William Whistler and Dan Thomas join us to study for PhDs. Konrad Dąbrowski takes up a position as a postdoctoral researcher.
Moving on, moving in Summer 2012: Viresh Patel has left us to take up a research position with the Graph Theory group at Birmingham University. We welcome Nicholas Georgiou who will replace him. We also bid farewell to Artem Pyatkin who leaves us for the Sobolev Institute of Mathematics in Russia, Petr Golovach who joins the Algorithms Research Group at the University of Bergen and Barnaby Martin who takes up a lectureship at the School of Engineering and Information Sciences at Middlesex University.
Invited Talk Magnus Bordewich will be an invited speaker at this year's Colloquia in Combinatorics in London.
Comings and Goings January 2012: Maximilien Gadouleau joins the group as a new lecturer. He joins us from Queen Mary and has research interests in various aspects of coding, cryptography and combinatorics. Ross Kang is leaving us to take up a research fellowship at CWI in Amsterdam. Yonghong Xiang is leaving for Beijing, China to work for China Aerospace Science and Technology Corporation where he will lead a research and development group focused on image processing and parallel computing for Unmanned Aerial Vehicles (UAVs). Catherine Greenhill has joined us for a six month visit collaborating principally with Magnus Bordewich.
Arrivals October 2011: Daniel Allsop, Aidan Chalk and Alan Heppenstall have joined ACiD as postgraduate students.
PhD Awarded September 2011: Congratulations to Lars Nagel on the award of his PhD for his thesis on randomised load balancing. Lars will soon be taking up a postdoc position at Johannes Gutenberg University Mainz.
New Lecturer We welcome George Mertzios to the School. George was previously a Research Fellow at the University of Haifa and has research interests in various aspects of algorithms and complexity including foundations of networks, combinatorial optimization and algorithmic game theory. See his homepage for more information.
Fellowship Daniel Paulusma has been awarded a Sir Derman Christopherson / Sir James Knott Foundation Fellowship by Durham's Institute of Advanced Study. The fellowship covers the period October to December 2011.
New Students Sepehr Meshkinfamfard and Foad Lotfifar join us as PhD students working on the SCALUS project.
Paper at SOCG Ross Kang's paper Sphere and dot product representations of graphs (joint with Tobias Muller) has been accepted at Symposium on Computational Geometry, the flagship conference for geometric algorithms.
REF Panel Iain Stewart has been selected to serve on the REF 2014 assessment panel for Computer Science and Informatics.
Paper at LICS Barnaby Martin's paper A tetrachotomy for positive first-order logic without equality (joint with former Durham colleague Florent Madelaine) has been accepted at Logic in Computer Science. This is the fourth consecutive year that Barnaby has had at least one paper at this prestigious conference.
Award for Paper Magnus Bordewich (and his co-author Charles Semple) have received the Discrete Applied Mathematics top cited article 2005-2010 award from Elsevier for their paper entitled Computing the minimum number of hybridisation events for a consistent evolutionary history.
Invited Talk at LICS Andrei Krokhin will be an invited speaker at the 26th Logic in Computer Science in June 2011.
Arrivals and Departures October 2010: Laurence Dawson, Jeremy Kemp, Robert Powell and Adam Symonds join ACiD as postgraduate students; Anna Huber comes to Durham as a postdoctoral researcher. Berndt Muller leaves to take up a Senior Lectureship at Glamorgan.
Invited Talk at CLS Andrei Krokhin gave an invited talk at Computer Science Logic in August 2010.
PhD Awarded May 2010: Congratulations to Pim van 't Hof on the award of his PhD for his thesis on exact algorithms. Pim will soon be taking up a postdoc position at the University of Bergen.
Most Cited Paper Andrei Krokhin was awarded the Top Cited 2005-2010 Paper Award by Discrete Applied Mathematics for the paper Supermodular functions and the complexity of Max CSP (joint with D.Cohen, M.Cooper, and P.Jeavons).
Best Paper Award Daniel Paulusma (and co-authors Asaf Levin and Gerhard Woeginger) won the Grover-Klingman Prize for the best paper in the journal Networks in 2008 for their pair of papers The Computational Complexity of Graph Contractions I, II.