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

Seminars from previous years: 2017/18  2016/17  2015/16  2014/15  2013/14  2012/13  2011/12  2010/11

See also NODES activities.

ACiD Seminars 2018/19
Term 1
Thurs 11 Oct 2018
13:00 in E360



Thurs 18 Oct 2018
13:00 in E360
Maximilien Gadouleau (Durham)
Decision problems for digraphs inspired by Boolean networks
Show Abstract

Abstract: This talk aims to introduce some of my research and to get interest from researchers in algorithms and complexity (notably of graph problems); as such, it will be fairly relaxed and informal. A Boolean network is a function from {0,1}^n to itself. It is an abstract model for a network of interacting entities, where each entity has a Boolean state that evolves over time according to a deterministic update function. The architecture of the Boolean network is given by its interaction graph, which indicates which update function depends on which states. The main general problem is: how does the interaction graph of a Boolean network affect its dynamics? In this talk, we are interested in the problem of finding a Boolean network with a given interaction graph that satisfies some interesting dynamical properties (e.g. many fixed points, or nilpotence). This yields some new decision problems on digraphs, whose complexities are so far unknown.

Thurs 25 Oct 2018
13:00 in E360
Sergey Kitaev (Strathclyde)
The role of computer experiments in the theory of word-representable groups
Show Abstract

Letters x and y alternate in a word w if after deleting in w all letters but the copies of x and y we either obtain a word xyxy... (of even or odd length) or a word yxyx (of even or odd length). A graph G=(V,E) is word-representable iff there exists a word w over the alphabet V such that the letters x and y alternate in y iff xy in E. Word-representable graphs generalise several important classes of graphs such as circle graphs, 3-colourable graphs and comparability graphs.
After an introduction to the theory of word-representable graphs, in this talk, I will discuss the impact on the theory of computer experiments.

Thurs 8 Nov 2018
13:00 in E360



Thurs 15 Nov 2018
13:00 in E360
Pawel Rzazewski (Warsaw)
TBA

Thurs 22 Nov 2018
13:00 in E360



Thurs 29 Nov 2018
13:00 in E360



Thurs 6 Dec 2018
13:00 in E360
Carl Feghali (Bergen)
TBA

Thurs 13 Dec 2018
13:00 in E360
Joanna Ochremiak (Cambridge)
TBA

Term 2
Thurs 17 Jan 2019
13:00 in E360



Thurs 24 Jan 2019
13:00 in E360
Sebastian Ordyniak (Sheffield)
TBA

Thurs 31 Jan 2019
13:00 in E360



Thurs 7 Feb 2019
13:00 in E360



Thurs 14 Feb 2019
13:00 in E360



Thurs 21 Feb 2019
13:00 in E360
Marianne Johnson (Manchester)
TBA

Thurs 28 Feb 2019
13:00 in E360



Thurs 7 Mar 2019
13:00 in E360



Thurs 14 Mar 2019
13:00 in E360



Thurs 21 Mar 2019
13:00 in E360