Algorithms

Algorithms group photoThe Algorithms group

The Algorithms Group focuses on designing and analysing algorithms that solve computational problems efficiently. Group members combine techniques from computer science, discrete mathematics, and probability theory in algorithms research spanning the following areas:

Theory of Bio-Inspired Algorithms covers general-purpose optimisation paradigms that draw inspiration from biological systems. Evolutionary algorithms mimic Darwinian principles such as survival of the fittest to artificially evolve candidate solutions for optimisation and design problems. Swarm intelligence paradigms such as ant colony optimisation or particle swarm optimisation are based on the collective intelligence of animal swarms. We work on providing a theoretical foundation for understanding the working principles of these heuristic algorithms through quantifying how quickly they find satisfactory solutions for various problems. This exposes how performance depends on algorithmic parameters and design choices, and helps to design better bio-inspired optimisation algorithms.

Deblurring illustrationDeblurring recovers image detail from blurred images.

Numerical Algorithms: One of the most important problems in geometric modelling is the calculation of the points of intersection of curves and surfaces. Tangential points of intersection are of particular interest, but they are difficult to compute reliably because multiple roots of a polynomial are extremely sensitivity to noise. We use methods for the computation of multiple roots of polynomials to develop better methods for deblurring images because a blurred image is formed by the convolution of an exact image and a point spread function, and the product of two polynomials is formed by the convolution of their coefficients.

Parameterized Algorithms are exact algorithms for computational hard problems that exploit the structuredness of real-world instances to solve certain instances of these problems much more efficiently. Since almost every real-world instance comes with more information than just its input size in bits, the parameterized approach allows a much more fine-grained analysis of the complexity of computational problems than the classical P vs NP-framework. Our group employs the parameterized approach for a wide range of problems in computer science such as satisfiability, constraint satisfaction, integer linear programming, planning, and problems on graphs and networks.

Efficient Graph Algorithms: Graphs are everywhere. Typical examples include Facebook/Twitter, Internet, Web graphs and brain networks. Many such graphs are extremely large, and are constantly changing, which poses great challenges for efficiently analysing their structures. We aim to tackle these challenges through the design and analysis of graph algorithms in the modern computational models, including sublinear algorithms (e.g., property testing, streaming algorithms) that read or store only a small portion of the large input while still have provable performance guarantees, and dynamic algorithms that update efficiently the solution of a problem after dynamic changes over the graph.