ACiD, Algorithms and Complexity in Durham, is a world-leading research group 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 research foci including computational complexity, proof complexity, descriptive complexity, graph theory, exact algorithms, randomised algorithms, approximation algorithms, parameterized algorithms, finite model theory, constraint satisfaction, interconnection networks, universal algebra and mathematical logic.
50 Years of Satisfiability Prof. Andrei Krokhin has spoken on Thursday 8th April at the prestigious Simons Institute seminar 50 Years of Satisfiability: The Centrality of SAT in the Theory of Computing. The topic was "Classifying the Complexity of SAT and CSP: Are we there yet?" and a recording is accessible here.
Prague Logic Seminar Dr. Barnaby Martin will speak on Monday 29th March at the Logic Seminar of the Institute of Mathematics at the Czech Academy of Sciences. The seminar is about "Depth lower bounds in Stabbing Planes for combinatorial principles" and reports recent work with Nicola Galesi (Rome) and Stefan Dantchev and Abdul Ghani (Durham).
BCTCS 2021 Dr. Eleni Akrida is an invited speaker at the 37th British Colloquium for Theoretical Computer Science (BCTCS 2021). The event runs from 29-31 March and is hosted by Liverpool University but will be run online.
CSP Seminar Andrei Krokhin and Jakub Oprsal (together with Victor Dalmau) are organising the online seminar series CSP seminar with the first talk taking place on Wednesday 19 August 2020.
Temporal Graphs George Mertzios and Eleni Akrida will co-organise the satellite workshop Algorithmic Aspects of Temporal Graphs III at ICALP 2020, taking place on Tuesday 7 July 2020.
Gaetan Berthe We welcome Gaetan as stagiere from ENS Lyon for a (virtual) internship with Barnaby Martin, Siani Smith and Daniel Paulusma.
Congratulations to Dan Thomas for passing his PhD viva with minor corrections!
Dagstuhl Seminar George Mertzios will co-organise the seminar Temporal Graphs: Structure, Algorithms, Applications taking place April 25-30, 2021.
Leeds Logic Seminar Barnaby Martin gave the Leeds Logic Seminar on 12th February 2020 on "The complexity of quantified constraints".
Paper at STOC 2020 The paper of Barnaby Martin (co-authored with Dmitriy Zhuk from Charles University in Prague) "QCSP monsters and the demise of the Chen Conjecture", has been accepted at the 52nd ACM Symposium on Theory of Computing, which is the top world-wide conference for Theoretical Computer Science.
University of Patras George Mertzios gave a talk at the CEID social hour on Temporal Vertex Covers and Sliding Time Windows on Friday 13th December.
New Faculty Positions Applications are invited for academic positions in the Department of Computer Science. Details can be found here.
SICOMP Editorial Board Prof. Andrei Krokhin joins the editorial board of the prestigious SIAM Journal of Computing from 1st January 2020.
Saturday Morning Science Dr. Tom "The Power of Randomness" Friedetzky will give a talk on this eponymous topic in the Saturday Morning Science Series. The talk will take place at the Calman Learning Centre at 10.30am on 30th November 2019: more details can be found here.
New PhDs! ACiD welcomes new students Karl Southern (Durham) and Isobel Friedlander (Durham Maths), both to be supervised by Dr. Max Gadouleau.
New member ACiD welcomes Dr. Eleni Akrida from Liverpool University. Dr. Akrida joins the department as Assistant Professor (Teaching) with a wealth of experience in graph algorithms and complexity, as well as approximation algorithms and probabilistic analysis of algorithms.
Paper at FOCS 2019 The paper of Andrei Krokhin and Jakub Oprsal "The complexity of 3-colouring H-colourable graphs" has been accepted at the 60th Annual IEEE Symposium on Foundations of Computer Science, which is one of the two top world-wide conferences for Theoretical Computer Science (the other being STOC).
New Postdoc ACiD welcomes Dr. Nick Brettell from Eindhoven University of Technology who has come to work with Matthew Johnson and Daniel Paulusma on the Leverhulme Trust project Efficient Graph Colouring Algorithms via Input Restrictions.
LMS-NZMS Aitken Lecture On Wednesday 3rd July we welcome Prof. Bakh Koussainov (University of Auckland, New Zealand) to Durham to give a lecture on Algorithmically random structures. More information can be found here.
Paper at CCC 2019 The paper of Stefan Dantchev and Barnaby Martin "Resolution and the binary encoding of combinatorial principles" (co-authored with Nicola Galesi from La Sapienza in Rome), has been accepted at the 34th Computational Complexity Conference, which will be held at Rutgers (New Brunswick, NJ) in July,
Paper at STOC 2019 The paper of Andrei Krokhin and Jakub Oprsal "Algebraic approach to promise constraint satisfaction" (co-authored with Jakub Bulin from Charles University in Prague), has been accepted at the 51st ACM Symposium on Theory of Computing, which is the top world-wide conference for Theoretical Computer Science.
Postdoc Position Applications are invited for a postdoctoral position for one year to work with Matthew Johnson and Daniel Paulusma on Efficient Graph Colouring Algorithms via Input Restrictions. Details can be found here.
Computational Biology in Durham Announcing the inaugural Durham 'Computational Biology' symposium.
Paper at AAAI-2019 The paper of George Mertzios and Viktor Zamaraev "Sliding Window Temporal Graph Coloring" (co-authored with Hendrik Molter from the TU Berlin), has been accepted for presentation at the 23rd AAAI Conference on Artificial Intelligence (AAAI-19), which is world-wide in the two top conferences in AI, having an acceptance rate of 16.2% this year.
New PhDs! ACiD welcomes new students Abdul Ghani (Durham) and Siani Smith (Warwick).
ACRI Max Gadouleau gave a talk on Friday 21st September at ACRI 2018 in Como, Italy.
BCTCS 2019 & AlgoUK The 35th British Colloquium for Theoretical Computer Science will be held in Durham on 15th-17th April 2019, incorporating AlgoUK on 15th-16th April: BCTCS & AlgoUK 2019.
Old Codgers Matthew Johnson will speak at the Old Codgers' Combinatorial Colloquium in Reading on 7th November.
AlgoUK Liverpool George Mertzios will speak at the 2nd AlgoUK meeting in Liverpool on 20th September.
Computability in Europe 2019 We will host the 15th International Conference on Computability in Europe in Durham on 8th-12th July 2019: CiE 2019.
Seminaire LIMOS Barnaby Martin gave the Alcoloco seminar at the Universite de Clermont-Auvergne on Wednesday 27th June. The title was "Mettre le Q dans CSP" or "The complexity of quantified constraints".
Promising Andrei Krokhin and Daniel Paulusma have been awarded a three-year EPSRC grant for work on The Complexity of Promise Constraint Satisfaction. Their proposal was ranked first at a very competitive Prioritisation Panel.
Invited Talk Andrei Krokhin will speak at the Computational Complexity Conference in San Diego in June.
Combinatorics Workshop Viktor Zamaraev will be speaking at the British Mathematical Colloquium in June.
Dagstuhl Daniel Paulusma is organizing a workshop in July 2019 on Graph Colouring: from Structure to Algorithms.
Satellite George Mertzios is organizing a satellite workshop of ICALP 2018 on Algorithmic Aspects of Temporal Graphs.
Playing Away On 6 December, Tom Friedetzky will trek over to Maths to give a Statistics Seminar.
Doctoral Success Congratulations to Chris Wastell on passing his PhD examination.
AlgoUK now has a website and has announced its first workshop at King's College London, 6-7 February 2018.
NODES We host the organisation's next meeting on 29 November: our own Iain Stewart and Tom Nye (Newcastle University) will be speaking. Full details here. A couple of weeks later, we will participate in the NODES Industry Day.
Seminar On 24 October, Barnaby Martin gave a talk in the St Andrews School of Computer Science on The Complexity of Quantified Constraints.
Workshop George Mertzios has been invited to talk at GROW 2017 (Workshop on Graph Classes, Optimization, and Width Parameters).
Welcome We are pleased to greet two new members of the group: Viktor Zamaraev joins us as a postdoctoral researcher, and Giacomo Paesani will study for a PhD.
Graphs and Networks Course A ten week course on Spectra and Geometry of Graphs and Networks begins at 1pm on 9 October. It is being led by Norbert Peyerimhoff as a MAGIC (Mathematics Access Grid Instruction and Collaboration) course.
ALGOUK Iain Stewart and Daniel Paulusma have won an EPSRC grant that will fund a range of activities to bring together researchers on algorithms in the UK and facilitate interactions with researchers in other disciplines and industry.
Congratulations to Aidan Chalk on a successful outcome to his PhD examination. Aidan has taken up a position with the Science and Technology Facilities Council.
Symposium Our colleagues in Maths are organizing a meeting on Markov Processes, Mixing Times and Cutoff.
Congratulations to Tom Friedetzky on promotion to Associate Professor.
Talks Barnaby Martin gave the York Semigroups Seminar on 3 May discussing his work on generating sets for powers of finite algebras. He also gave the Séminaire ALGO at the Université de Caen Normandie on 23 May.
Success We congratulate Anthony Stewart on the outcome of his PhD viva.
Journal Iain Stewart has joined the Editorial Board of Philosophical Transactions of the Royal Society A which was founded in 1660 and is the world's first scientific journal.
Book Andrei Krokhin and his collaborator Stanislav Zivny have edited an open-access volume of surveys on The Constraint Satisfaction Problem: Complexity and Approximability.
Invited Speaker In September, Daniel Paulusma will be talking at the Cycles and Colourings workshop in Slovakia.
Conference George Mertzios and Iain Stewart are on the Programme Committee of I-SPAN 2017, the 14th International Symposium on Pervavise Systems, Algorithms, and Networks that takes place in Exeter in June.
Scotland In April, Max Gadouleau will be talking at the Scottish Combinatorics Meeting 2017.
Café Society Barnaby Martin will give an informal talk about his research at Cafe Scientifique Durham City.
Research Funding George Mertzios has been awarded an EPSRC grant for his project on Algorithmic Aspects of Temporal Graphs.
Off Again After a busy year with us, André Nichterlein returns whence he came (Berlin).