Algorithms and Complexity in Durham
A research group in the Department of Computer Science


NODES Seminar Max Gadouleau is talking in Durham about Finite Dynamical Systems at a meeting of the recently-launched Northeast Organisation of DisreteE Structures (NODES), a newly-founded group of Mathematicians and Computer Scientists from Newcastle and Durham.

Invited Talk In December, Daniel Paulusma will speak at 100 Years of Matching Theory in Hungary.

Visit Barnaby Martin was invited by Oxford University's Algorithms and Complexity Theory Group to talk to them about his work on The Complexity of Quantified Constraints.

Congratulations to Ioannis Lignos on a successful PhD viva.

Sabbatical We welcome Cédric Gerot from Grenoble Alpes Univeristy who will spend 2016-17 with us as a research visitor.

Welcome Back to Rob Powell who rejoins the School as a Teaching Fellow after recently completing his PhD with us.

Prizewinner Congratulations to André Nichterlein for winning Best Presentation at the School's Research Day 2016 for his talk Parameterized algorithms: only for NP-hard problems?

Record Breakers Daniel Paulusma and undergraduate student David Allison have found new lower bounds for the famous Snake-In-The-Box problem (finding longest induced paths in hypercubes). See their paper or their position in the pantheon.

Higginson Lecture On 16 November, the School welcomes Rob Pieké to deliver this annual prestigious lecture.

New Doctorate Congratulations to Nihan Tokac on the successful outcome of her PhD viva.

New Lecturer We welcome back Barnaby Martin to our group. Barnaby joins us from Middlesex University. His research is in computational and proof complexity, logic, constraint satisfaction and SAT solving.

Grant Daniel Paulusma (PI) and Matthew Johnson (CI) have been awarded a grant by the Leverhulme Trust to support their work on graph colouring algorithms.

Graph Theory Workshop The group are hosting Algebraic, Topological and Complexity Aspects of Graphs Cover 2017 in January. See the meeting's website for further details.

Congratulations to Max Gadouleau and Matthew Johnson on promotion to Senior Lecturer.

Success Congratulations to Carl Feghali on the outcome of his PhD viva. In the Autumn, Carl will take up a postdoctoral position with the Fondation Sciences Mathématiques de Paris.

Moving On We bid farewell to Alonso Castillo-Ramirez who leaves us for the University of Guadalajara.

Congratulations to Sepehr Meshkinfamfard on the achievement of passing his PhD.

New Postdoc André Nichterlein joins ACiD from Technische Universität Berlin to work with George Mertzios.

Well done to Foad Lotfifar on the successful outcome of his PhD viva.

Elected Congratulations to Iain Stewart on his election as Programme Secretary of the London Mathematical Society.


Congratulations to Rob Powell on a successful PhD viva.

Algebra Connections The Department of Mathematical Sciences in Durham is hosting a one-day workshop on Interactions between algebra, coding theory and cryptography on 5 January 2016.

Speaker Max Gadouleau has been invited to present his work at the next meeting of the North British Semigroups and Applications Network in November.

Keynote Andrei Krokhin will give an invited lecture at the 31st British Colloquium of Theoretical Computer Science in September.

Invited Talk Magnus Bordewich will speak at Imperial College's workshop on Mathematical Approaches to Evolutionary Trees.

Symposium Durham's Department of Mathematical Sciences is hosting a meeting on Permutation Groups and Transformation Semigroups in July and ACiD members Max Gadouleau and Alonso Castillo-Ramirez have been invited to give talks.

PhD Success Congratulations to Laurence Dawson on the award of his doctorate.

Congratulations to Daniel Paulusma on his promotion to Professor and to George Mertzios on his promotion to Senior Lecturer.

Best Paper Congratulations to PhD student Foad Lotfifar and his coauthors for winning the best paper award at SustainIT2015 for their work on smart grids.

New Researcher Alonso Castillo-Ramirez joins ACiD to work with Max Gadouleau on his project Memoryless Computation and Network Coding.

Farewell to Archontia Giannopoulou who moves on to another postdoc position at the Warsaw Center of Mathematics and Computer Science.

Invited Talk Daniel Paulusma will be speaking at WG2015 in June.

Dagstuhl Andrei Krokhin is organizing a meeting on The Constraint Satisfaction Problem: Complexity and Approximability in July 2015.


Arriving Welcome to David Kirk who joins the group to study for an MSc by Research.

Invited Talk Max Gadouleau will talk on Points fixes des réseaux Booléens et théorie des codes at a workshop in Nice in November 2014.

Graph Colouring Alejandro Erickson has painted some pictures for us to hang on the wall.

Talks Konrad Dąbrowski has set up a series of Computer Science Junior Seminars for postdocs and PhD students to present ongoing research.

Grant Max Gadouleau has been awarded Royal Society funding to support work with Adrien Richard from Nice University on Boolean Networks, Network Coding and Memoryless Computation.

Welcome to Archontia Giannopoulou who joins us as a Research Associate.

Congratulations to Daniel Allsop on the award of MSc (Research).


Elected Iain Stewart has been elected as a member of the Executive of UKCRC (the UK Computing Research Committee) and to the Council of the London Mathematical Society.

Network Coding In recognition of the recent appointment of Max Gadouleau, we will be hosting a meeting on Network coding, partitions and security on 20 November.

Ins and Outs At the start of the new academic year, we welcome to ACiD postdocs Alejandro Erickson and (for a second time) Konrad Dąbrowski, and PhD students Carl Feghali, Anthony Stewart, Nihan Tokac and Chris Wastell, and we bid farewell to Anna Huber who takes up a lectureship at the University of Derby.

Research Funding Max Gadouleau has been awarded an EPSRC grant to fund his project Memoryless Computation and Network Coding.

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 Daniel Paulusma on his promotion to Reader.

Farewell to researchers Konrad Dąbrowski and Nicholas Georgiou who have moved on to further postdoctoral positions in, respectively, the ESSEC Business School in France and the Department of Mathematics here in Durham.

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.

Grant Success George Mertzios and Iain Stewart have been awarded large EPSRC grants to support their work on, respectively, intersection graph models and interconnection networks.

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.