skip to content

Department of Computer Science and Technology

 

Algorithms and Complexity research theme logo

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