Algorithms are fundamental objects of study in computer science. Algorithmic processes are not only executed in digital electronic computers but occur everywhere in the world around us. The Algorithms and Complexity research theme focuses on the mathematical modelling and analysis of algorithmic processes. A particular interest is the study of the complexity (for example, the resource use) of such processes.
Within this theme, Anuj Dawar leads a group studying Logic and Algorithms. The emphasis is on the study of computational complexity through the lens of logical definability. That is to say, to establish lower bounds on the complexity of problems by examining how difficult it is to formally describe them. Tom Gur leads a research group studying Complexity Theory and Quantum Computing. This includes investigating the power and limitations of classical and quantum algorithms and their interplay with learning theory, coding theory, cryptography, and pure mathematics. Thomas Sauerwald leads a research group analysing the performance of random processes and developing new algorithms to cope with complex data sets. A common theme is the analysis of algorithms and complexity on graph-structured data and the underlying graph theory, for instance random walks on graphs and structural aspects of graph isomorphism.
Related Links
- Algorithms and Complexity Seminar. Our group's main seminar series
- Algorithms. Part 1A course
- Complexity Theory. Part 1B course
- Quantum Computing. Part II course
- Advanced Algorithms. Part II course
- Topics in Logic and Complexity. Part III and MPhil ACS course
