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 wordrepresentable 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 wordrepresentable iff there exists a word w over the alphabet V such that the letters x and y alternate in y iff xy in E. Wordrepresentable graphs generalise several important classes of graphs such as circle graphs, 3colourable graphs and comparability graphs.
After an introduction to the theory of wordrepresentable 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 
