# Our Research Groups

Research groups are connected if they have a researcher in common. Thick lines indicate a strong connection with at least 3 researcher in common.

For more information about the research groups * CLICK ONE* of the buttons below:

### Tilings, lattices, and crystals

*David Bourne, Anna Felikson, Herbert Gangl, John Hunton, Peter Jorgensen, John R Parker, Norbert Peyerimhoff, Bernard Piette, Pavel Tumarkin, Alina Vdovina*

Tilings show up in discrete geometry as well as optimal configurations in materials sciences (minimizing global energy functions). If periodic, tilings often give rise to discrete groups and lattices, and we study these lattices with regards to additional properties like arithmeticity and their connection with hyperbolic geometry, topology and number theory. Tilings of Euclidean and hyperbolic spaces appear also as substructures (apartments) in Tits buildings (named after Jacques Tits), which can be studied both with combinatorial/topological methods as well as methods from geometric group theory. Aperiodic tilings (and associated moduli spaces and dynamical systems) are not only interesting theoretical objects but appear also in the real world in the form of quasicrystals.

### Algebraic and logical structures

*Stefan Dantchev, John Fitzgerald, Leo Freitas, Victor Khomenko, Andrei Krokhin, Barnaby Martin, Sarah Rees, Jason Steggles, David Stewart, Iain Stewart
*

An applied use of algebraic and logical structures is on automated theorem proving for both computer systems/software verification, as well as mathematical theories.

Computational and Proof Complexity of Logical Theories as well as Logical and Algebraic techniques in studying Constraint Satisfaction Problems.

### Optimisation and Approximation

*David Bourne, Camila Caiado, Ostap Hryniv, Ian Jermyn, Victor Khomenko, Andrei Krokhin, George Mertzios, Andrew Wade*

Many computational problems amount to finding a discrete object satisfying a specified set of constraints and optimising some parameter of a solution. We study the mathematical structure of such problems that leads to efficient exact approximation algorithms.

### Algorithmic Graph Theory

*Magnus Bordewich, Max Gadouleau, Ioannis Ivrissimtzis, Maciej Koutny, Matthew Johnson, Barnaby Martin, George Mertzios, Boguslaw Obara, Daniel Paulusma, Norbert Peyerimhoff, Iain Stewart, Alina Vdovina*

The notion of an algorithm is a key foundational concept in Computer Science, with the measurement of the resources used in the implementation, that is, the computational complexity, central to the study of algorithms.

Graphs and abstract representations of objects and relationships are widely used to model computer networks, biological networks, physical systems, data structures and many other real world applications.

We study structural properties of graphs such as their expansion and clusters using, for example, spectral methods and sparsity, and the relationship between these graph properties and the efficiency of algorithms for solving various graph-theoretic problems.

### Probabilistic systems

*Magnus Bordewich, Camila Caiado, John Fitzgerald, Leo Freitas, Tom Friedetzky, Ostap Hryniv, Ian Jermyn, Tom Nye, Bernard Piette, Andrew Wade*

Discrete systems in nature, computer science and engineering are often inherently random. Probabilistic models and methods are important in the context of complex networks, randomized algorithms, and statistical inference for complex models. There are links to computational geometry, combinatorics, statistical physics, and complexity theory.

*Example:*

Magnus Bordewich and Tom Nye are working on combinatorial algorithms for reconstructing phylogenies from DNA data, and mathematical models for comparing and manipulating them. Image courtesy of Magnus Bordewich (Durham)

### Biological structures

*Magnus Bordewich, Leo Freitas, Tom Friedetzky, Ostap Hryniv, Victor Khomenko, Maciej Koutny, Marta Pietkiewicz-Koutny, **George Mertzios, Tom Nye, Boguslaw Obara, Bernard Piette, Jason Steggles*

We use discrete mathematical theories to analyze biological data and to model biological structures. These theories include graph theoretical models and algorithms, as well as dynamical systems. They are used to model cell network structures (such as the cytoskeleton) and evolution, epidemiology and others.

*Example:*

In collaboration with biologists, Boguslaw Obara and Bernard Piette are working on the mathematical modelling of the cytoskeleton discrete structure. Image courtesy of Tim Hawkins, Joanne Robson (Durham) and Rudolf Leube (Aachen)

### Vision and Graphics

*Camila Caiado*, *Stefan Dantchev, Herbert Gangl, Ioannis Ivrissimtzis, Ian Jermyn, Boguslaw Obara*

Discrete models of images, geometry, and shape (surface meshes, random fields, graphs, …), applied to problems in computer vision and graphics (image segmentation, surface reconstruction and refinement, graph matching, 3D printing, …)

### Concurrent Systems: Design and Verification

*Stefan Dantchev, John Fitzgerald, Leo Freitas, Victor Khomenko, Maciej Koutny, Marta Pietkiewicz-Koutny, Jason Steggles*

Sequential systems belong to the last millennium. Concurrent systems, on the other hand, are ubiquitous today. Ranging from multicore processors to heterogeneous, distributed and cyber-physical systems, they share a unifying principle of computational and physical processes that interact to achieve a common goal.

Our goal is to develop methods and software tools that meet the challenges posed by modern concurrent systems, including:

- Unifying modelling frameworks that reflect the hybrid and diverse characteristics of these systems, including structural, computational, probabilistic and physical aspects.
- Efficient verification techniques for key properties related to performance, safety, security and resilience.
- Automatic synthesis of concurrent systems from behavioural specifications.
- Machine-assisted exploration of the design space and specification-based testing.

### Representations, Triangulations, and Mutations

*Martina Balagovic, Anna Felikson, Herbert Gangl, Ioannis Ivrissimtzis, Peter Jorgensen, Stefan Kolb, Andrew Lobb, Sarah Rees, Dirk Schuetz, David Stewart, Pavel Tumarkin*

Triangulations are objects studied in geometry, combinatorics, and computer science. Flipping an edge changes one triangulation to another. This is an example of a mutation as known from cluster algebras, which were designed to study modern aspects of Lie theoretical objects. A particularly important class of such objects are quantum groups arising as deformations of universal enveloping algebras.

### Automata and Dynamical Systems

*Camila Caiado*, *Michael Dritschel, Andrew Duncan, Max Gadouleau, John Hunton, Evgenios Kakariadis, Maciej Koutny, John R Parker, Bernard Piette, Sarah Rees*

Many phenomena can be configured as dynamical systems that evolve in discrete time much like a collection of frames from a motion picture. Examples include processes ranging from the micro-/macro-cosmos to programming in theoretical computer science. Automata theory provides the appropriate language to quantify and measure the intrinsic properties of such systems; notions like the entropy and the zeta function are often distinguishing invariants. This setup applies especially to encoding symmetries and modelling complex (real-life) processes that are used in biology, engineering and artificial intelligence.

### Groups and Computation

*Andrew Duncan, Anna Felikson, Herbert Gangl, Barnaby Martin, John R Parker, Norbert Peyerimhoff, Sarah Rees, David Stewart, Iain Stewart, Pavel Tumarkin, Alina Vdovina*

We use a variety of methods to investigate decision problems over groups and semigroups including formal languages and automata, rewriting systems, group actions on topological spaces, simplicial and CW-complexes. These allow us to understand some of the algorithmic properties of many classes of groups (hyperbolic and relative hyperbolic groups, Artin groups, universal groups of pregroups etc.) On the practical side of this theory we study and implement algorithms to compute with particular groups and to give concrete bounds on complexity of problems that may arise in coding and cryptography theory. Another aspect of group computation concerns discrete groups acting on symmetric spaces (for example PSL_2(Z[i]) acting on hyperbolic 3-space). The fundamental domain arising from this action has interesting geometric and arithmetic properties (in the case at hand polyhedral decomposition and volume, respectively). In several cases these properties may be computed, leading on theoretical side, as times, to elements in algebraic K-theory and on the very practical side to models of highly symmetric polytopes (which have been 3D-printed).

### Knots, Braids, and Geometry

*Martina Balagovic, Ioannis Ivrissimtzis, John Hunton, Stefan Kolb, Andrew Lobb, John R Parker, Norbert Peyerimhoff, Dirk Schuetz, Alina Vdovina*

Geometrical objects such as knots and braids form a class of important mathematical structures. We use techniques of geometry, graph theory, homological algebra and stable homotopy theory to study these and higher dimensional generalisations.