Algorithm design and analysis
Algorithms are the foundation of computing, driving the efficiency and capability of modern systems.
We focus on fundamental questions surrounding the design and analysis of algorithms to solve complex computational problems. We mathematically prove performance bounds such as time and space complexity to guarantee the efficiency and reliability of our algorithms. Beyond theoretical advances, we apply these insights to the development of modern, high-performance computing systems and to data-driven applications where scalability and robustness are critical.
Our research
Our core research topics include
- Approximation and online algorithms are two approaches to solving computational problems with restricted resources. Many (if not most) computational problems are NP-hard. Given such a problem, we do not expect an algorithm that produces an optimal solution to all inputs efficiently (i.e., in polynomial time). Nevertheless, we still need to solve many of these problems in practice, e.g., multi-drop delivery schedules, so we are happy to accept approximation algorithms: efficient algorithms that output a solution that is provably close to optimal. In contrast, many problems are presented to us online (piece by piece) requiring irrevocable decisions before seeing the whole input; think of placing blocks in the game
- Streaming and sublinear algorithms focus on designing algorithms for massive datasets where storing or processing the entire input is infeasible. Streaming algorithms handle data sequentially using only very limited memory, for example, maintaining approximate statistics over network traffic. Sublinear algorithms produce approximate solutions by examining only a small portion of the input, for example, estimating the size of a graph property without scanning every edge. These approaches are central to modern large-scale computation, where efficiency depends not only on running time but also on memory and data access.
- Randomized algorithms make use of random bits in addition to the input when computing a solution. It is not clear at first how the addition of random bits can help in solving a computational task, however for many problems the fastest known algorithms are randomized (sometimes the only known algorithms!). Randomized algorithms have been used to solve problems in all the settings described above, and they are especially useful for breaking symmetry, avoiding unfavourable orderings and exploring complex solution spaces.
- Algorithms for computing systems seek to solve problems efficiently and correctly on complex architectures that extend beyond a sequential machine, such as distributed, parallel, cloud, and external memory architectures. These settings all pose their unique challenges, which make many standard design choices inefficient or impossible in practice. For example, in distributed computing a network of individual machines without shared global state must work together to compute the solution to a problem where the input may itself be distributed across the machines. This leads to many issues such as time ordering, consensus, and data placement.
People
- Dr Georgios Birmpas
- Professor Martin Gairing
- Professor Leszek Gasieniec
- Dr Nikhil Mande
- Dr Anish Mukherjee
- Dr Lutz Oettershagen
- Professor Igor Potapov
- Dr William Rosenbaum
- Professor Rahul Savani
- Professor Paul Spirakis
- Dr Joachim Spoerhase
- Dr Karteek Sreenivasaiah
- Dr John Sylvester
- Dr Stuart Thomason
- Dr Konstantinos Tsakalidis
- Dr Sebastian Wild
- Professor Prudence Wong
- Dr Viktor Zamaraev
Opportunities
We welcome opportunities to engage with students, researchers, and industry partner:
- PhD opportunities: please contact us if you are interested in pursuing a PhD in algorithm design and analysis
- Consultancy and research collaborations: we welcome partnerships, consultancy, and knowledge exchange projects with academic, industry, and government partners.
Contact us
Please discuss with relevant academic staff if you are interested in their research.