# Complexity Theory and Algorithmics Group

## Algorithmics and Computational Complexity

What is harder: to classify web pages according to their
relevance to a user, or to sort them into rank order? To win at
chess or to win at checkers? Why do we believe that modern
cryptosystems are hard to break? What's the best way to
process a database query so that the response is as fast as
possible?
Question of this nature can be made mathematically meaningful,
which permits a mathematical analysis to be applied to proposed
algorithms, independently of experimental results.
This kind of analysis belongs to
two closely-related research fields: *algorithmics*,
the design of algorithms with provable performance guarantees,
and *computational complexity*, the classification of
problems according to the kinds of algorithms that can solve
them.

This research is divided into subfields that address more specific classes of problems, or models of computation. But the common set of ideas and analytical tools lead to extensive interaction amongst apparently diverse subfields of algorithmics and computational complexity.

## The contribution of CTAG

The following are some of the subfields within which CTAG is particularly active.

*Distributed computing* seeks
ways to manage the interactions between multiple interacting
computer systems. Distributed computing aims to

- exploit the potential for speedup resulting from multiple applications working on the same task
- identify techniques for mediating between multiple applications so as to guarantee correctness and avoid deadlock
- work out ways to ensure fault-tolerance.

*Randomised algorithms* make use of random numbers
to ensure that certain guarantees hold for any input,
with high probability. These algorithms
have been applied in many diverse settings. Much of our work in
CTAG focuses on Markov-chain mixing times, and proof techniques
that certain methods are able to sample from classes of
combinatorial structures sufficiently quickly,
in an unbiased manner. Specifically
this work applies to models of physical systems, such as the
Anti-ferromagnetic Potts model.

Other work by CTAG relating to randomised algorithms includes algorithmic problems involving random graphs, random structures arising in biology, and work on randomised algorithms for broacasting in radio networks.

*Computability theory and formal models of computation.*
Computability theory is the branch of the theory of computation that
studies the limits of computing devices by analysis of different models
of computation.
It is possible to show clear limits to the ability of computers, even
given arbitrarily vast computational resources, to solve even seemingly
simple problems. Work on computability theory by members of the group
includes results on automata theory, decision problems for matrix
semigroups and reachability problems for different computational models.

*Bioinformatics* is amalgamate of mathematics, computer science,
biochemistry, biology and other closely related fields. Most of
the work in bioinformatics refers to

- development and advancement of discrete algorithms,
- creation of computational and statistical techniques, and
- theory of natural processes

## Recent Publications

## Current and Previous Research Grants

These are listed in our Projects page.

## Scientific collaboration

Members of CTAG have a large number of national and international research collaborators; we do not maintain a comprehensive list here, but they may be found by checking the co-authors of individual members of the group.