| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | July 30, 2012 |
| Latest Amendment Date: | July 30, 2012 |
| Award Number: | 1217256 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Jack S. Snoeyink
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | August 1, 2012 |
| End Date: | July 31, 2015 (Estimated) |
| Total Intended Award Amount: | $399,984.00 |
| Total Awarded Amount to Date: | $399,984.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
4333 BROOKLYN AVE NE SEATTLE WA US 98195-1016 (206)543-4043 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
185 Stevens Way Seattle WA US 98195-2350 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Algorithmic Foundations |
| Primary Program Source: |
|
| Program Reference Code(s): |
|
| Program Element Code(s): |
|
| Award Agency Code: | 4900 |
| Fund Agency Code: | 4900 |
| Assistance Listing Number(s): | 47.070 |
ABSTRACT
Geometric spaces arise in computer science through a number of avenues. The most obvious of these occurs when the input data for a problem possesses an inherent metric structure, like the hop-distance between nodes in a network, or the similarity distance between pairs of genomic sequences. But there are other, more subtle examples, like the geometry of sparse vectors, which arises prominently in coding theory, signal recovery, and quantum information, or the effective resistance distance between nodes in an electrical network, which has proven to be a powerful algorithmic tool in attacking both algebraic and combinatorial problems.
Perhaps most strikingly, in the setting of combinatorial optimization, high-dimensional geometry often presents itself in an unexpected and profound manner. A basic example is the use of convex optimization in the solution---exact or approximate---to a variety of combinatorial problems. In many cases, a problem with an a priori purely combinatorial structure is shown to involve rich geometric phenomenon. Furthermore, we now realize that often this structure is inherent and fundamental, in the sense that any solution to the problem must confront its geometric core.
The PI will seek to understand these connections and develop new algorithmic techniques to exploit them. This work will employ techniques from high-dimensional geometry and probability, functional analysis, spectral geometry, and combinatorics to attack problems at the forefront of computer science. This includes addressing fundamental gaps in our understanding of theoretical issues, as well as developing solutions to practical problems that arise from the need to analyze and manipulate massive data sets. To achieve these goals, the investigator intends to address central, important open problems in the fields of approximation algorithms, high-dimensional information theory, and discrete asymptotic convex geometry.
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.
PROJECT OUTCOMES REPORT
Disclaimer
This Project Outcomes Report for the General Public is displayed verbatim as submitted by the Principal Investigator (PI) for this award. Any opinions, findings, and conclusions or recommendations expressed in this Report are those of the PI and do not necessarily reflect the views of the National Science Foundation; NSF has not approved or endorsed its content.
This project was largely considered with the mathematical structures underlying the design of efficient algorithms, and the nature of computational intractability--why certain problems appear fundamentally difficult to solve. Over the course of the project, we discovered many remarkable connections with problems in probability, physics, and high-dimensional geometry. For instance, methods from quantum information theory and machine learning were used to show that small semi-definite programs cannot solve NP-complete problems. Stochastic calculus (a tool commonly employed in mathematical finance) was used to study the geometry of Boolean functions. And techniques from metric geometry were applied to understand routing problems in certain models of wireless networks.
To expound on one of these directions, consider a regular n-gon in the plane. Somewhat remarkably, this body with n sides is the shadow of a body in higher dimensions that has only log(n) facets. In fact, this phenomenon underlies many efficient algorithms: Small linear programs can sometimes capture exponentially complicated polytopes (the generalization of a convex polygon to higher dimensions). This allows us to optimize over these polytopes, leading to solutions to a vast array of problems of interest.
There are certain polytopes associated to difficult computational problems (like the traveling salesman problem) that we do not expect to be the shadow of a simple convex body. The PIs and coauthors have found a proof that, indeed, this cannot be the case, even if one uses even more complicated bodies (called spectrahedra) that have infinitely many "facets."
Last Modified: 10/29/2015
Modified by: James R Lee
Please report errors in award information by writing to: awardsearch@nsf.gov.
