| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | June 24, 2011 |
| Latest Amendment Date: | June 24, 2011 |
| Award Number: | 1111257 |
| Award Instrument: | Standard 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, 2011 |
| End Date: | August 31, 2016 (Estimated) |
| Total Intended Award Amount: | $772,845.00 |
| Total Awarded Amount to Date: | $772,845.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
150 MUNSON ST NEW HAVEN CT US 06511-3572 (203)785-4689 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
150 MUNSON ST NEW HAVEN CT US 06511-3572 |
| 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
This project will exploit algebraic properties of operators associated with graphs in an integrated set of research and educational activities designed to develop new mathematical and algorithmic techniques; apply these to the solution of real-world problems and longstanding theoretical questions in mathematics, computer science, biology, and physics; and make these techniques broadly known and accessible to students, researchers, and practitioners in many fields.
This research has its origins in spectral graph theory, which studies how the eigenvalues and eigenvectors of the graph Laplacian (and other related matrices) interact with the combinatorial structure of the graph. Spectral graph theory has been one of the great success stories in both the theory and practice of algorithm design. It has led to fundamental advances in graph partitioning, web search (notably including Google's PageRank algorithm), the understanding of random processes and the algorithms derived from them, the construction of error correcting codes, derandomization, convex optimization, machine learning, and many others.
While the eigenvalues and eigenvectors of the Laplacian capture a striking amount of the structure of the graph, they certainly do not capture all of it. Recent work by the principal investigators and other researchers suggests that theoretical computer scientists have only scratched the surface of what can be done if they are willing to broaden their investigation, extending it to study more general algebraic properties of the Laplacian than just its eigenvalue structure, and more general operators than just the Laplacian.
Under this award, the principal investigators will build a research program across the three universities involved in this proposal to develop such a theory and its applications. This initiative has the potential to provide transformative advances in a range of theoretical and applied areas of computer science, including:
* Faster algorithms for fundamental graph problems, such as Maximum Flow, Minimum Cut, Minimum Cost Flow, Multicommodity Flow, approximating Sparsest Cut, generating random spanning trees, and constructing low-stretch spaning trees.
* Better algorithms for the analysis of data, with potential applications to the Unique Games Conjecture.
* Faster algorithms for solving broad classes of important linear systems, both sequentially and in parallel.
* Faster distributed algorithms for information dissemination in networks.
* A spectral and algebraic graph theory for directed graphs, based on ideas from differential geometry.
* Novel quantum algorithms for a large class of problems that appear to be hard for classical computers.
* New techniques for problems in Quantum Physics based on ideas developed in Computer Science and Combinatorics.
The principal investigators will also work to disseminate these techniques by developing courses, training undergraduate and graduate students, and introducing these ideas to scientists in other fields.
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.
The major scientific results supported by this award may be roughly divided into 3 categories:the improvement of algorithms for solving systems of linear equations;the design of new algorithms for solving problems in Statistics and Machine Learning;the solution of problems at the intersection of Pure Mathematics, Numerical Linear Algebra,and Quantum Physics.
The need to solve systems of linear equations arises throughout disciplines includingComputational Science, Image Processing, Machine Learning, Optimization, and OperationsResearch. We have developed significantly faster algorithms for solving Laplacian linear equations,one of the types that appear most often in applications. We have also generalized these algorithmsso that they can handle many other important families.
In Statistics, we have developed significantly faster algorithms for classic isotonicregression problems. These are related to algorithms we designed to solve novel inferenceproblems in Machine Learning. The algorithms we designed allow one to solve much larger problemsthan was previously conceivable.
While working on the design of algorithms for solving systems of linear equations, we developed a mathematicaltechnique that has allowed us to solve a problem from the mathematical foundations of Quantum Physicscalled the Kadison-Singer Problem. This problem was known to be equivalent to fundamental problemsin a number of fields of Pure and Applied Mathematics, including Operator Theory, Number Theory,Frame Theory, and Discrepancy Theory. These problems are thus now all solved, and researchers are workingto understand their implications.
We have disseminated knowledge of these developments by organizing workshops and conferences,presenting talks at conferences, and by writing survey and tutorial papers and by posting lecture notes on-line.
Last Modified: 11/20/2016
Modified by: Daniel A Spielman
Please report errors in award information by writing to: awardsearch@nsf.gov.
