Computer Laboratory

Old ACS project suggestions

Project suggestions in other areas

Characterising Logarithmic Space Complexity

Originator: Anuj Dawar

This is a project in the field of descriptive complexity, which seeks to characterise computational complexity classes through definability in logic. There are long-standing open questions in the field about whether complexity classes corresponding to feasible computation (such a polynomial-time and logarithmic-space classes) have such characterisations. On the other hand, logical characterisations of polynomial-time are known on special classes of graphs, such as trees and planar graphs. This project will attempt to obtain similar results for the logarithmic-space classes. The key method will be to examine algorithms for the graph isomorphism problem on these classes of graphs and determine in what logical formalism they can be expressed.

Computational Modeling of bacterium Tubercolosis metabolism

Originator: Pietro Lio

The goal of the project is to analyze a genome-scale model of metabolism for the organism Mycobacterium tubercolosis which causes tubercolosis (TB). TB is the most frequent co-infection in patients infected by the human immunodeficiency virus type 1 (HIV-1). The emergence of drug-resistant variants of the bacterium is calling to measure to prevent the global spread of the deadly TB strains. Analysis of the genome model generates hypotheses about co-regulation of the genes that catalyze metabolic reactions and become targets for antibiotics. The analysis of the model may be relevant to therapy assessments and to efforts in synthetic biology to engineer genomes. The hypothesises about co-regulation can be translated into proposals for regulatory control in novel genomes. The project will be based on the genome-scale modeling using the stoichiometric matrix and on available microarray data together with probabilistic model checking approaches.