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

Here you can find details of research projects that are currently active within ACiD. We would welcome applications for PhD positions relating to any of these areas (see also the department's list of prospective PhD projects).

  • Algorithms and Complexity in Phylogenetics
    Phylogenetics is the study of the relationships between species using DNA or protein sequence data. This project is developing novel algorithms for reconstructing phylogenetic networks representing reticulate evolution (i.e. non-treelike evolution including hybridisations or lateral gene transfer), from genetic distance data (the measured difference between the DNA sequences of the the species).

  • Constraint Satisfaction Problems (CSPs)
    CSPs provide a uniform way of expressing many computational problems by using systems of constraints that need to be satisfied simultaneously. Examples include systems of equations, propositional satisfiability problems, graph colourings and graph homomorphisms. Some of these problems are tractable and some are hard from a computational complexity point of view. This project is to develop the mathematical, especially algebraic, theory of the complexity of constraints. It is aimed at understanding what mathematical structure makes a problem (within the CSP paradigm) computationally easy or hard.

  • Boolean Networks, Network Coding and Memoryless Computation
    Boolean networks are used to model many kinds of networks of interacting entities, such as gene regulatory networks or neural networks. This project is devoted to the study of the dynamics of Boolean networks and on their computational power. Its innovation comes from the use of techniques from graph theory, information theory (network coding) and algebra (memoryless computation).

  • Memoryless Computation and Network Coding
    Network coding is a revolutionary technique to transmit data through a network. Unlike routing, network coding lets the intermediate nodes combine the messages they receive, thus achieving a higher throughput. Memoryless computation is a new paradigm for computing functions of the registers of a processing unit without any communication with the memory. It can be seen as the analogue of network coding for computing. This project is devoted to the study of memoryless computation (computing time, minimum number of instructions required, etc.) and uses techniques from network coding and algebra (transformation semigroups).

  • Steganography and Steganalysis
    Steganographic algorithms embed digital signatutes into digital media in a way that the very existence of the embedded signature remains hidden. Steganalytic algorithms are their counterparts, aiming at detecting the existence of embedded signatures. Typical applications of steganography include copyright protection, integrity authentication and covert communications. This project develops steganographic and steganalytic algorithms for 3D models.
    • Dr Ioannis Ivrissimtzis is working on this project in collaboration with Dr Ying Yang and Professor Holly Rushmeier from Yale University.
    • We developed the first universal and the first specific steganalytic algorithm for 3D models.

  • Topology, Geometry and Laplacians of Simplicial Complexes
    Simplicial complexes play a prominent role in several fields of mathematics. They appear as triangulations of surfaces, or more general higher dimensional spaces, and they are used for the computation of topological invariants such as the Euler characteristic and the fundamental group. As a consequence of their simplicity and versatility, simplicial complexes are widely used as geometric representations in the fields of industrial design and medical imaging. In this project, we aim at generalizing the geometric concept of curvature into simplicial complexes.

  • Balls into Bins Protocol
    The "balls into bins" protocol is a very well known paradigm in probabilistic algorithms. In its simplest form one randomly allocates a set of identical balls among a set of identical bins, and asks questions about the resulting load distribution. It underlies a great many applications, e.g., hashing or load balancing. In this project we will focus on its applicability in load balancing, generalising the basic protocol/model so as to be able to capture real-life requirements like non-identical balls, non-identical bins, or dependencies among either balls or bins.

  • Voting Protocols
    In the original problem, we are given a network of players modelled as a graph. Each node starts with one initial opinion from a finite set of possible opinions. If eventually all nodes agree on one opinion we say this opinion wins and the process converges. Typically, one would demand from such a voting procedure to run accurately, that is, the opinion with the largest initial support should win with decent probability, and to be efficient, that is, the voting process should converge within as few communication steps as possible. Additionally, voting algorithms are usually required to be simple, fault-tolerant, and easy to implement.
    Distributed voting algorithms have applications many fields. In distributed computing, these include consensus and leader election. Early results in other areas can be attributed to distributed databases where voting algorithms have been used to serialize read and write operations. In game theory, distributed voting is used to analyze social behaviour. Various processes based on the majority rule were analysed in the study of influence networks, and they have been used to measure the competition of opinions in social networks. Variants are applied to distributed community detection. In computational sciences, voting processes can be utilised to model chemical reaction networks, neural and automata networks, and cell behaviour in biology.

  • Mathematical Properties of Interconnection Networks
    Interconnection networks form the interconnection topologies for networks arising in parallel and distributed computing, typically in networks-on-chips, distributed-memory multiprocessors and data centre networks. As such they need to support, for example, routing, flow control, packet switching, fault tolerance, scalability, high throughput, low latency, energy efficiency and different traffic patterns. The graph-theoretic properties of interconnection networks have a strong correlation with their performance as interconnection topologies with relevant properties including connectivity, hamiltonicity, pancyclicity, symmetry, isoperimetric properties, embeddability and numerous variations. This project is to further examine mathematical aspects of interconnection networks not only in relation to their role as interconnection topologies but also as combinatorial objects in their own right.

  • Algorithmic and Structural Properties of Special Graph Classes
    This is an ongoing project that captures a number of studies into graph-theoretic problems originating from Computer Science, Economics and Mathematics. Many such problems are computationally hard in general. By exploiting the graph structure we aim to find efficient algorithms for special graph classes or else to obtain new intractability results. In this way we hope to identify the reasons for computational hardness of a problem, which will increase our understanding of how to deal with more general inputs.

  • Algorithmic Aspects of Intersection Graph Models
    One important way of representing specific classes of graphs is using an intersection model: every vertex of the graph is assigned a set, and there is an edge between two vertices if the two corresponding sets have a non-empty intersection. Some intersection models provide a natural and intuitive understanding of the structure of a class of graphs, and turn out to be very helpful in the design of efficient algorithms that solve optimization problems. Therefore, it is of great importance to establish non-trivial intersection models for families of graphs. Many well-known graph classes can be described as intersection graphs of families derived from some kind of geometric configuration. Probably the most prominent example is that of interval graphs, which are the intersection graphs of intervals in the real line. A natural generalization of the above concept of intersection graphs is to allow some tolerance in the intersections: in this case there is an edge between two vertices if the two corresponding sets intersect by more than a specific threshold. The main goal of this project is to investigate the computational complexity (i.e. either to provide efficient algorithms or to prove computational hardness, both in the exact and in the parameterized sense) of fundamental discrete optimization problems on important intersection graph classes and their tolerance counterparts.

  • Complexity of Reconfiguration Problems
    The reconfiguration graph of a combinatorial decision problem contains as nodes all possible solutions to the problem, and two solutions are adjacent if their difference is minimal (for example, for the problem of colouring a graph, two solutions are adjacent if the colours differ on exactly one vertex). This project investigates finding algorithms (or hardness proofs) for the problem of deciding whether solutions are connected in reconfiguration graphs and looks at connections to the complexity of the underlying problem.

  • SCALUS (SCALing by means of Ubiquitous Storage)
    Storage research increasingly gains importance based on the tremendous need for storage capacity and I/O performance. Over the past years, several trends have considerably changed the design of storage systems, starting from new storage media over the widespread use of storage area networks, up to grid and cloud storage concepts. Furthermore, to achieve cost efficiency, storage systems are increasingly assembled from commodity components. Thus, we are in the middle of an evolution towards a new storage architecture made of many decentralized commodity components with increased processing and communication capabilities, which requires the introduction of new concepts to benefit from the resulting architectural opportunities. The consortium of this Marie Curie Initial Training Network (MCITN) "SCALing by means of Ubiquitous Storage (SCALUS)" aims at elevating education, research, and development inside this exciting area with a focus on cluster, grid, and cloud storage.

  • Distributed, Collaborative Systems
    The focus of this research project will be on the study of distributed and collaborative systems a group of agents communicating with one another and acting according to what they learn. These are systems without any central control, in which tasks are accomplished through simple interactions. Such systems exist in many areas: social networks where people influence their friends, sensor systems collecting data, robot swarms, epidemics, or distributed systems in the more usual sense of a large number of processors connected via a network performing a task.
    The objective of this research program is two-fold. First, to study these collaborative and distributed systems. Second, to develop new mathematical methods that can be used to formally analyse these systems. These methods will be helpful in other areas of computer science, like game theory and the analysis of local search algorithms.