| EPSRC Reference: |
GR/M96940/01 |
| Title: |
SHARPER ANALYSIS OF RANDOMISED ALGORITHMS: A COMPUTATIONAL APPROACH |
| Principal Investigator: |
Goldberg, Professor L |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Warwick |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 June 2000 |
Ends: |
31 May 2003 |
Value (£): |
66,793
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
| Statistics & Appl. Probability |
|
|
| 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.warwick.ac.uk |