Funded projects

Recently funded projects

• AlgoUK: A Network for Algorithms and Complexity in the UK
  • Principal Investigator; EPSRC grant EP/R005613/1; Dec. 2017-Nov. 2020; value £108,682
    “The notion of an algorithm is perhaps the key foundational concept in Computer Science, with the measurement of the resources used by algorithms and their implementations, that is, their computational complexity, central to their study and application. As the amount of available data explodes across science, technology, and society, and new potential applications emerge, never has it been so important that research in algorithmics, the science of algorithms, translates into effective implementations and that the weight of algorithmics research is brought to bear on new potential applications. However, often deep theoretical insights and advances do not rapidly percolate ‘upwards’ into real-world implementations and ‘sideways’ into other academic domains. On the other hand, algorithmic problems emerging within industry, science, and society do not always percolate ‘downwards’ to the theoreticians who have the tools and techniques to provide improved algorithmic solutions. Moreover, the boundary between Computer Science and other subjects is becoming ever more fluid. The key aim of the AlgoUK network of researchers is to facilitate multi-faceted interactions within the UK’s algorithmic research community and also inter-disciplinary interactions between these researchers and those in industry and other subjects such as Mathematics, Biology, and Chemistry. The founding research groups, and hosting sites for the workshops, are at Durham, Kings College London, Leicester, Liverpool, Royal Holloway, and Warwick, but the network is open to all who wish to engage with it.“

• Interconnection Networks: Practice unites with Theory (INPUT)
  • Principal Investigator; EPSRC grant EP/K015680/1; Sept. 2013-Sept. 2016; value £353,575
    “The practical construction of, for example, a supercomputer that might fill a large room is immensely complex, with a multitude of wires, cables, boards, chips, racks and cabinets all conjoined so that all of the computational power of such a system can be employed to yield efficient solutions to problems on massive data sets. The design of such a hardware and software system is an incredible feat of engineering. Mathematicians abstract the essential interconnection network within such a supercomputer as a graph. Whilst this may seem an imprecise abstraction, one can use graph-theoretic properties in order to design interconnection network topologies which possess many properties one would wish of an interconnection network. Graph properties relating to, for example, symmetry, shortest-paths, connectivity, Hamiltonicity, recursive decomposability and embeddings prove to be extremely important in securing good practical properties for interconnection networks. However, up until now there has been a considerable gap between the mathematical theory on the one hand and practical interconnection network performance on the other. Our research proposal aims to narrow this gap by providing a closer link between the theory and practice of interconnection networks, with the ultimate goal being techniques by which we can theoretically design an interconnection network and be sure of its resulting practical properties when built and used.“
  • This project was in collaboration with Professor Steve Furber, Dr. Javier Navaridas, and Dr. Mikel Luján in the Advanced Processor Technologies research group at the University of Manchester.
  • There were two Post-doctoral Research Assistants employed on this project: Dr. Alejandro Erickson at Durham; and Dr. Abbas Kiasari at Manchester.
• Detecting Induced Graph Patterns
  • Co-Investigator (PI: Professor Daniel Paulusma); EPSRC grant EP/K025090/1; Sept. 2013-Sept. 2016; value £363,442
    “We consider the following four elementary graph operations: vertex deletions; edge deletions; edge contractions; and vertex dissolutions. Combining these four graph operations leads to ten essential graph containment relations, and each graph containment relation corresponds to a decision problem: subject to the specified containment relation, does a graph G contain some graph H? One of the most important and fundamental achievements of Theoretical Computer Science and Discrete Mathematics is Robertson and Seymour’s Graph Minor Project where a structural characterization of graphs without a forbidden minor is derived. Their theory has led to deep results across Computer Science and Mathematics. An important consequence of their theory is that any containment problem allowing edge deletions can be efficiently solved. Our over-arching aim is to develop a theory, similar to that of Robertson and Seymour, but on induced containment relations, i.e., when edge deletions are not permitted graph operations. As techniques that are useful for their non-induced counterparts can no longer be applied, a basic theory for induced containment relations, similar to the Graph Minor Project of Robertson and Seymour, is largely absent. Our research proposal aims to change this.“
  • There was a Post-doctoral Research Assistant employed on this project: Dr. Konrad Dąbrowski.

The following are projects that finished in the not too distant past:

• Quantified Constraints and Generalisations
  Principal Investigator; EPSRC grant EP/G020604/1; Sept. 2009-Aug. 2012; value £247,539
• Tolerating Faults in Interconnection Networks for Parallel Computing
  Principal Investigator; EPSRC grant EP/G010587/1; Feb. 2009-Jan. 2012; value £275,210

(updated 2nd January 2022)