| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 9, 2015 |
| Latest Amendment Date: | June 9, 2015 |
| Award Number: | 1514339 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Tracy Kimbrel
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2015 |
| End Date: | May 31, 2017 (Estimated) |
| Total Intended Award Amount: | $600,000.00 |
| Total Awarded Amount to Date: | $291,908.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
450 JANE STANFORD WAY STANFORD CA US 94305-2004 (650)723-2300 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
Stanford CA US 94305-2004 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
01001718DB NSF RESEARCH & RELATED ACTIVIT 01001819DB NSF RESEARCH & RELATED ACTIVIT |
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
A central endeavor of theoretical computer science is to classify computational problems according to the resources (such as running time and storage space) needed to solve them. Although the field of algorithm design has been highly successful in discovering efficient, polynomial-time algorithms for problems of practical interest, little evidence has been shown for the optimality of most algorithms. The goal of this project is to build a useful complexity theory for the class of polynomial-time solvable problems (called P), by proving equivalences between problems and proving conditional lower bounds on specific problems, assuming the validity of certain plausible mathematical conjectures.
Known lower bounds for specific problems in P are conditioned on some complexity-theoretic assumption such as the (Strong) Exponential Time Hypothesis (concerning the complexity of k-CNF-SAT), the conjecture that dense all-pairs shortest paths (APSP) requires cubic time, or that 3SUM requires quadratic time. The goals of this project are threefold. The first goal is to establish conditional lower bounds on problems in diverse areas (such as graph optimization, string matching, geometry, and dynamic data structures) using standard hardness conjectures. The second goal is to search for better hardness conjectures that are both plausible and versatile, and to discover relationships (implications or equivalences) between nominally unrelated conjectures. The last goal is to investigate the plausibility of these conjectures by attempting to disprove them.
The curricular portion of this project involves developing lecture material suitable for introductory algorithms and complexity courses at both the undergraduate and graduate level.
PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH
Note:
When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external
site maintained by the publisher. Some full text articles may not yet be available without a
charge during the embargo (administrative interval).
Some links on this page may take you to non-federal websites. Their policies may differ from
this site.
Please report errors in award information by writing to: awardsearch@nsf.gov.
