EPSRC logo

Details of Grant 

EPSRC Reference: GR/M96957/01
Title: SHARPER ANALYSIS OF RANDOMISED ALGORITHMS:A COMPUTATIONAL APPROACH
Principal Investigator: Jerrum, Professor M
Other Investigators:
Researcher Co-Investigators:
Project Partners:
Department: Sch of Informatics
Organisation: University of Edinburgh
Scheme: Standard Research (Pre-FEC)
Starts: 01 January 2000 Ends: 30 June 2003 Value (£): 102,799
EPSRC Research Topic Classifications:
EPSRC Industrial Sector Classifications:
No relevance to Underpinning Sectors
Related Grants:
Panel History:  
Summary on Grant Application Form
Analysis of algroithms is a central activity of Computer Science. Interestingly, understanding the behaviour of complex algorithms can often be aided by the application of computations itself. Such applications may arise in at least 2 ways. First, the most obviously, computation is a useful means of gaining intuitions or insites which may later be proven mathematically. Second, and perhaps more important, is that computation can be used as a proof technique in itself. Often the proof of claims covering instances of unbounded size can be reduced to generating and checking a large number of cases of fixed size. Where the cases are not too numerous, this provides a powerful proof technique. Perhaps the most famous example of this type of proof by computation is the four-colour theorem. It is our intention to explore these uses of computation in the context of design and analysis of randomisation algorithms. Our fundamental tool will be computation, and our fundamental goal will be developing new methods for designing and analysing randomised algorithms. The goal fits in with several aspects of EPSRCs mission including the support of high quality basic research and the advancement of knowledge.
Key Findings
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Potential use in non-academic contexts
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Impacts
Description This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Summary
Date Materialised
Sectors submitted by the Researcher
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk
Project URL:  
Further Information:  
Organisation Website: http://www.ed.ac.uk