Below are the proposals funded by MathFIT as a result of the MathFIT 2000 Call (text is included to give a flavour of the intended research).
Algebraic Structural Methods and Complexity of Constraint Satisfaction
Investigator: Dr. Pete Jeavons (Oxford University)
"This proposal will enable Dr. Bulatov and Dr. Krokhin of Ural State University, Russia, to work with Dr. Peter Jeavons at the University of Oxford. Dr. Bulatov and Dr. Krokhin are specialists in algebra, and especially the theory of clones and universal algebra, and this project is designed to explore how recent results and methods from universal algebra can be linked to the study of the broad family of computational problems known as 'constraint satisfaction problems'. This family of problems has been widely studied in computer science, and there have been many attempts to characterise restrictions on the general problem which make it possible to solve it efficiently. It appears that considerable further progress with this question could now be made using structural results from universal algebra, and this project will develop the necessary theory. One novel feature of the approach is that it includes both finite constraint satisfaction problems (such as graph colouring problems and satisfiability problems) and infinite constraint satisfaction problems (such as temporal and spatial reasoning problems). By taking an abstract, algebraic, approach we plan to develop a framework which naturally incorporates both types of problems (which have traditionally been studied separately) and so obtain a more powerful theory of the computational complexity of these important problems."
Investigators: Professor David Epstein (Warwick)
"We plan to use geometric ideas to find the average of a collection of trees. (Each edge of each given tree has a positive length.) To make the computations feasible for large examples and fast for small examples, we will need to develop new algorithms for the manipulation of trees and associated data. We will produce user-friendly software, which will serve as a module in existing software, improving the facilities available to biologists. We will work with biologists to ensure that the software continues to develop along useful lines."
Constraint Programming, Search and Symmetry
Investigators: Dr. Ian Gent, Dr. Steve Linton, Professor Ursula Martin (St Andrews), Profesor Barbara Smith (Huddersfield)
"We aim to make progress in particular constraints solving by drawing together three strands of research: mathematical results concerning group actions on spaces of Boolean functions and related topics; the powerful techniques of computational group theory that allow effective computation, even in very large groups in actions of high degrees; and the successful and industrially important technique of constraint programming. We will develop a new constraint modelling language and new solving techniques, to express and exploit the symmetries of the problem. We will apply these developments to combinatorial problems and real world problems containing symmetry, such as sports scheduling, balanced incomplete block designs, template design, and car sequencing. As well as these practical developments, the projects will explore the novel algebraic and algorithmic questions that arise from the interaction of symmetry, inference, and search."
Digital Descriptions for Serial Data Streams
Investigators: Professor Terry Lyons, Dr. Ben Hambly (Oxford)
"Sampling a continuously varying data stream and then reproducing the signal adequately, is a frequent computing challenge? An audio recording should reproduce the sounds created in the studio. A recording of the wind patterns should allow one to test the design of a bridge. What data should one collect? The traditional approach would be to take linear samples from the data stream. If the data is vector valued, the theory of 'systems driven by rough paths' suggests it might be more sensible to use more complex algebraic proxies for the data stream over short time intervals. We want to develop the maths arising from this novel perspective that the incremental path segments of a continuous data stream can be coded efficiently using elements chosen from a nilpotent Lie group labelled via their Lie representation. Open questions of strategic importance include: 'Does the iterated integral sequence determine the path?' (cf. identification problem for Fourier Series); and 'How should one extrapolate back from increments to a continuous stream (invert the transform)?'. We will keep this project informed and focussed through computational examples such as the compression of stereo sound."
Genetic Algorithms in Computational Group Theory
Investigator: Professor Alexandre Borovik (UMIST)
"The project is aimed at the analysis of a new class of cryptographic primitives based on word problems in groups, by means of genetic algorithms applied to the practical solution of word problems. We shall concentrate on a systematic experimental study of genetic algorithms for the conjugacy search problem in braid groups because of its importance for cryptographic applications. We shall compare the behaviour of genetic algorithms on several closely related classes of groups where the deterministic version of the problem has complexity varying from trivial (symmetric groups) to potentially very high (Artin groups). We aim either at the development of efficient algorithms, which would allow us to attack group based cryptographic primitives, or (which is a less spectacular but more likely outcome) at an identification of and an experimental and theoretical study of obstructions to convergence of genetic algorithms. This will require theoretical refinements and effective implementations of computations with different normal forms and length functions on braids, Coxeter and Artin groups."
Invariant Properties of String Rewriting Systems
Investigators: Professor Steve Pride (Glasgow)
"String rewriting systems are a basic concept in theoretical computer science, and also arise in various contexts in algebra. Our project is concerned with developing geometric techniques, especially in higher dimensions, to study rewriting systems, and applying these techniques to certain questions concerning 'nice' types of rewriting systems. Other techniques involving chains of ideas in commutative rings will also be developed and applied."
Kan - A Categorical Approach to Computer Algebra
Investigator: Dr. Neil Ghani (Leicester)
"Current computer algebra packages suffer from two main drawbacks: i) they are limited to specific problem domains; and ii) often they are limited to finite algebraic structures. This project will tackle these problems by developing a categorical specification language for uniformly modelling problems and using a rewriting based model of computation applicable to infinitary algebraic structures. The success of this project will be its ability to solve problems in the mathematical and computer science communities. Therefore we will develop Kan in consultation with clients whose input will ensure the project remains focused upon the solution of their problems. In addition, we shall use a number of optimisations to guarantee the efficiency of the end product."