|
| EPSRC Reference: |
GR/S76151/01 |
| Title: |
Discontinuous Behaviour in the Complexity of Randomized Algorithms |
| Principal Investigator: |
Professor ME Dyer |
| Other Investigators: |
|
| Researcher Co-investigator: |
|
| Project Partner: |
|
| Department: |
Sch of Computing |
| Organisation: |
University of Leeds |
| Scheme: |
Standard Research |
| 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 |
|
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.
|
| Final Report Summary |
|
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.
|
| Further Information: |
|
| Organisation Website: |
http://www.leeds.ac.uk |
|
|