| EPSRC Reference: |
GR/M12308/01 |
| Title: |
COMPLEXITY LOWER BOUNDS FOR ALGEBRAIC COMPUTATION MODELS |
| Principal Investigator: |
Vorobjov, Professor N |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Mathematical Sciences |
| Organisation: |
University of Bath |
| Scheme: |
Standard Research (Pre-FEC) |
| Starts: |
22 March 1999 |
Ends: |
21 May 1999 |
Value (£): |
4,000
|
| 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 |
|
Establishing a complexity lower bound is an essential part of a comprehensive procedure of design and analysis of computer algorithms. The proposed research aims to developing new methods of proving lower bounds for comparisons, or evaluating elementary transcendental functions, as elementary steps. These methods are based on differential-geometric study of accepting sets, which are semialgebraic or semi-Pfaffian. Before recent works of the VF and one of the Investigators, the main tools for producing lower bounds for this sort of problems were topological, with estimating parameters being sums of Betti numbers is also not appropriate. The proposed research will view polyhedrons and arrangements as stratified manifolds and will attempt to obtain new lower bounds in terms the number of faces of all dimensions by providing a compact description of smooth strata.
|
|
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.bath.ac.uk |