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
to solve abstract and practical problems posed by or inspired from the management and analysis of biological data.

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.