| EPSRC Reference: |
EP/I011528/2 |
| Title: |
Computational Counting |
| Principal Investigator: |
Goldberg, Professor L |
| Other Investigators: |
|
| Researcher Co-Investigators: |
|
| Project Partners: |
|
| Department: |
Computer Science |
| Organisation: |
University of Oxford |
| Scheme: |
Standard Research |
| Starts: |
01 July 2013 |
Ends: |
28 February 2014 |
Value (£): |
88,031
|
| EPSRC Research Topic Classifications: |
| Fundamentals of Computing |
Logic & Combinatorics |
|
| EPSRC Industrial Sector Classifications: |
| No relevance to Underpinning Sectors |
|
|
| Related Grants: |
|
| Panel History: |
|
|
Summary on Grant Application Form |
|
Computational complexity is typically concerned with decision problems, but this is a historical accident, arising from the origins of theoretical computer science within logic. Computing applications, on the other hand, typically involve the calculation of numerical quantities. These applications broadly fall into two types: optimisation problems, in which the goal is to maximise or (minimise) the value of a function, and counting problems, broadly interpreted, by which we mean computing sums, weighted sums, and integrals including, for example, the expectation of a random variable or the probability of an event.This project will consider all aspects of computational counting, with a particular focus on foundational questions in computational complexity (characterising the inherent difficulty of problems) and the development of algorithmic techniques. The goal of the project is to provide a better understanding of the inherent computational difficulty of counting (including approximate counting) and to provide efficient algorithms where they exist.
|
|
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.ox.ac.uk |