Algorithms and complexity

Overview

The study of the design, analysis and implementation of algorithms is at the heart of computer science. It is difficult to envision any large-scale computer application, such as an operating system, compiler, large-scale database system or computer graphics package that does not rely on the use of effective algorithms and data structures.

Researchers in our group explore a variety of algorithm types and areas of application. Applications include computational geometry, graph theory (including graph drawing), bioinformatics, learning theory, network routing, search engines, database systems, quantum computing, number theory and formal languages. Approaches include the study of randomized algorithms, adaptive techniques, approximation algorithms, fixed-parameter tractable algorithms and the mathematical analysis of the performance of algorithms, as well as issues of implementation. The organization and structuring of data, fundamental to the performance of most algorithms, is a major area of study.

Computational complexity is the study of the inherent limits of efficient computation measured in terms of time, space and other resources such as randomness. Our group includes researchers in various aspects of complexity theory including Kolmogorov complexity, as well as cryptography.