| EPSRC Reference: |
GR/S76151/01 |
| Title: |
Discontinuous Behaviour in the Complexity of Randomized Algorithms |
| Principal Investigator: |
Dyer, Professor ME |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
01 October 2004 |
Ends: |
30 September 2007 |
Value (£): |
112,946
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
|
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
The focus of our research is the common observation that computational problems may suddenly become much more difficult to solve when an (apparently) small change is made to some parameter describing the problem. Such a change in behaviour is often referred to as a phase transition, a term imported into computer science from statistical physics. We will examine the occurrence of this phenomenon in the area of randomized algorithms, where the progress of the computation is determined by selecting random bits. A particular emphasis will be placed on problems of randomly sampling and counting, where such parameterised problems and phase transitions have a long history of study in statistical physics. Understanding phase transitions in the complexity of algorithms is an important step in our understanding of algorithms and computational complexity. The EPSRC-funded International Review of UK Computer Science recently identified this as one of the two areas in need of increased support.
|
|
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.leeds.ac.uk |