Algorithms

The Algorithms Group focuses on the design and analysis of efficient algorithms, on classifying computational problems according to their difficulty such as their computational complexity, and on the analysis of general purpose heuristics from bio-inspired computation and artificial intelligence.

Algorithms research group staff members
On

Research Themes 

Theory of Bio-Inspired Computation and Artificial Intelligence

This topic covers general-purpose optimisation paradigms that draw inspiration from biological systems such as evolutionary algorithms, which are often successful when the performance of the best known problem specific algorithms is not as good as desired.  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 computational problems and AI applications such as combinatorial optimisation, algorithm configuration (parameter tuning), the evolution of the optimisation algorithm itself (hyper-heuristics and online parameter control) as well as the evolution of computer programs (genetic programming). This exposes how performance depends on algorithmic parameters and design choices including the benefits of populations of solutions and sexual recombination, and helps to design better bio-inspired optimisation algorithms.

Selected Recent Publications

G. T. Hall, P. S. Oliveto, D. Sudholt:
On the impact of the performance metric on efficient algorithm configuration.
Artificial Intelligence, Vol 303, 2022.

D. Corus, A. Lissovoi, P. S. Oliveto, C. Witt: 
On Steady-State Evolutionary Algorithms and Selective Pressure: Why Inverse Rank-Based Allocation of Reproductive Trials is Best.
ACM Transactions on Evolutionary Learning and Optimization, 1(1):1-38, 2021.

D. Corus, P. S. Oliveto: 
On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms.
Algorithmica, Vol. 82:3676-3706, 2020. 

A. Lissovoi, P. S. Oliveto, J. A. Warwicker: 
Simple Hyper-heuristics Control the Neighbourhood Size of Randomised Local Search Optimally for Leading ones.
Evolutionary Computation (ECJ), 28(3): 437-461, 2020.

A. Lissovoi, P. S. Oliveto: 
On the Time and Space Complexity of Genetic Programming for Evolving Boolean Conjunctions.
Journal of Artificial Intelligence Research (JAIR),  Vol.26: 655-689, 2019.

D. Corus, P. S. Oliveto, D. Yazdani: 
Artificial Immune Systems Can Find Arbitrarily Good Approximations for the NP-Hard Number Partitioning Problem.
Artificial Intelligence, Vol. 274:180-196, 2019.


Efficient Network Algorithms

In the realm of data explosion, it is usually the case that a single computational processor is unable to store a vast amount of data needed to do any meaningful computation. The data is generally distributed among a large number of processors/servers who need to communicate with each other via a network in order to perform various computational tasks. The recent trend in big-data is a case in point where the rapid acquisition of a vast amount of data makes it impossible for a single processing unit to handle.  Apart from big-data, this problem, and many of its variants, appear frequently in practice in many guises and in different levels of abstractions – in network protocols where the goal is to minimise the communication (and thereby error in the communication) between two network hubs, in VLSI circuit design where the goal is to minimise the energy used and to pack efficiently by decreasing the number of wires required, and also in data-structure, circuit complexity, auctions and a plethora of other interesting areas of study.

We tackle these challenges by designing (and proving the hardness of) efficient network algorithms in distributed models of computation, including communication protocols, query protocols, streaming algorithms, parallel algorithms and CONGEST algorithms. We use  various modern (graph) algorithm design and complexity techniques, such as spectral analysis, dynamic and distributed algorithms, as well as probability theory and linear algebra to achieve our goals.

Selected recent publications:

Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay, Danupon Nanongkai:
Breaking the quadratic barrier for matroid intersection. STOC 2021

Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai:
Distributed weighted min-cut in nearly-optimal time. STOC 2021

Sagnik Mukhopadhyay, Danupon Nanongkai:
Weighted min-cut: sequential, cut-query, and streaming algorithms. STOC 2020

The area of complexity theory deals with classification of computational problems with respect to their hardness of computation in various computational models. Our research group focuses on communication and query complexity where the model of computation does not allow random access to the input data (contrary to the traditional unit-cost RAM model); the data is usually stored implicitly or distributedly, and we are interested in how much information (via query access or communication) about the input data the solver needs in order to solve certain computational problems. We investigate this area of research by showing connections and interdependence between these complexity measures.

Selected recent publications:

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation Theorems via Pseudo-random Properties. Comput. Complex. 2019

Bruno Loff, Sagnik Mukhopadhyay:
Lifting Theorems for Equality. STACS 2019

Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation beats richness: new data-structure lower bounds. STOC 2018


Online Algorithms

An online problem is a problem whose input is revealed over time (for example, as a sequence of requests), and each piece of the input requires an immediate action (serving the request) that has to be chosen without knowledge of the future. Each action has an associated cost or profit, and the goal is to minimise the total cost or maximise the total profit. Due to the lack of information about the future, it is typically impossible to choose actions optimally, even if computational resources were infinite. However, for many online problems there exist algorithms whose solution value is guaranteed to approximate the in-hindsight optimum up to some bounded factor, regardless of the input.

Selected recent publications:

Christian Coester, Elias Koutsoupias:
The online k-taxi problem. STOC 2019

Christian Coester, James R. Lee:
Pure entropic regularization for metrical task systems. COLT 2019

Marcin Bienkowski, Jaroslaw Byrka, Christian Coester, Lukasz Jez:
Unbounded lower bound for k-server against weak adversaries. STOC 2020


Learning-Augmented Algorithms

The field of learning-augmented algorithms has emerged recently, motivated by the idea of combining the powers of worst-case analysis and machine learning. For an online problem as described above, suppose the algorithm receives as additional input some predictions about the future (obtained, for example, via machine learning heuristics on past data). Is it possible to incorporate these predictions in the algorithm design so that for good predictions, the algorithm produces a near-optimal solution, but it also avoids being misled by highly erroneous predictions and achieves the same worst-case guarantees as known from the setting without predictions? A positive answer has been found for a number of problems, but research in this direction is still young.

Selected recent publications:

Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, Bertrand Simon:
Online metric algorithms with untrusted predictions. ICML 2020

Antonios Antoniadis, Christian Coester, Marek Eliás, Adam Polak, Bertrand Simon:
Learning-Augmented Dynamic Power Management with Multiple States via New Ski Rental Bounds. NeurIPS 2021

Nikhil Bansal, Christian Coester, Ravi Kumar, Manish Purohit, Erik Vee:
Learning-Augmented Weighted Paging. SODA 2022


    Research group members

    Academic staff

    Affiliated staff

    Research staff

    Research students

    Seminars

    Upcoming seminars

    Details to be confirmed 

    Past Seminars

    2019

    May 21st, 2019
    14:00-15:00
    In COM-108 - Ada Lovelace Room.

    Some recent advances in dynamic graph algorithms
    Presented by Sayan Bhattacharya (University of Warwick).

    February 25th, 2019
    13:00-14:00
    In COM-G12-Blue.

    Hierarchical clustering: Objective functions and new algorithms
    Presented by Varun Kanade (University of Oxford)

    February 15th, 2019
    14:00-15:00
    In COM-G22-Blue.

    Geometric Semantic Genetic Programming
    Presented by Alberto Moraglio (University of Exeter)

    2018

    November 27th, 2018
    15:00-16:00
    In COM-G25.

    Testing logically defined properties on graphs of bounded degree
    Presented by Isolde Adler (University of Leeds)

    November 15th, 2018
    14:00-15:00
    In the Ada Lovelace Room.

    Algorithms for Out- and In-Branchings in Digraphs
    Presented by Gregory Gutin (Royal Holloway).

    November 19th, 2018
    14:00-15:00
    In the Ada Lovelace Room.

    Colouring Diamond-free Graphs
    Presented by Konrad Dabrowski (University of Durham)

    October 29th, 2018
    14:00-15:00
    In the Ada Lovelace Room.

    Finding Small Cuts in Dense Graphs
    Presented by Thomas Sauerwald (Cambridge University)

    October 17th, 2018
    15:00-16:00
    In the Ada Lovelace Room.

    Recent Advances on the Parameterized Complexity of Integer Linear Programming
    Presented by Sebastian Ordyniak.

    October 8th, 2018
    16:00-17:00
    In the Ada Lovelace Room.

    Graph Property Testing and Random Order Streams
    Presented by Pan Peng.

    July 27th, 2018
    15:00-16:00
    In the Ada Lovelace Room.

    Sunflowers and Quasi-sunflowers from Randomness Extractors
    Presented by Jiapeng Zhang (UC San Diego).

    July 9th, 2018
    12:00-13:00
    In COM-G25.

    Memetic Algorithms Beat Evolutionary Algorithms on the Class of Hurdle Problems
    Presented by Phan Trung Hai Nguyen (University of Birmingham).

    June 28th, 2018
    11:00-12:00
    In the Ada Lovelace Room.

    Spectral Sparsification and its Applications
    Presented by Dr. He Sun (University of Edinburgh).

    May 23rd, 2018
    11:00-12:00
    In the Ada Lovelace Room.

    Exact and Hybrid Approaches for Packing While Traveling and the Traveling Thief Problem
    Presented by Prof. Frank Neumann (University of Adelaide).

    Flagship institutes

    The University’s four flagship institutes bring together our key strengths to tackle global issues, turning interdisciplinary and translational research into real-world solutions.