| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | July 31, 2014 |
| Latest Amendment Date: | July 31, 2014 |
| Award Number: | 1423034 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Rahul Shah
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | August 1, 2014 |
| End Date: | July 31, 2018 (Estimated) |
| Total Intended Award Amount: | $229,142.00 |
| Total Awarded Amount to Date: | $229,142.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
11200 SW 8TH ST MIAMI FL US 33199-2516 (305)348-2494 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
10555 W Flagler St Miami FL US 33174-1630 |
| 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
Processing and analysis of large data sets presents substantial computational challenges. New computational models which distill the essence of computing over massive data sets are needed to address the challenges. "Local computation algorithm" (LCA) is a new computation model proposed by the PI and his collaborators. LCAs are randomized algorithms computing required portion of the output super-efficiently.
In this project, the PI aims to extend LCAs to new frontiers such as error correction codes, matrix analysis, approximation algorithms. The PI also plans to improve upon prior results by applying tools and techniques from other fields such as Monte Carlo Markov chains, online and distributed algorithms, and local graph partitioning.
The broader impacts of the project include mentoring of undergraduate and graduate students from under-represented groups in theoretical computer science and other computationally-oriented scientific 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.
Processing and analysis of large data sets presents substantial computational challenges, and calls for developing novel algorithmic tools and techniques which efficiently analyze and extract valuable information from big data.
To address this challenge, around 2010, the PI and his collaborators proposed a new computation model called "Local computation algorithm" (LCA). LCAs are randomized algorithms which, roughly speaking, are capable of super-efficiently computing what one needs and only what one needs. The aim of this project is to continue the study of algorithmic questions under the model LCA as well as other related questions for tackling big data.
In the four years (including a one-year no-cost extension) of the project, the PI and his collaborators have been working on designing and analyzing algorithms centered around LCAs, and proving lower bounds showing the limitations of different computation models for several problems. Our finds include a new error-correction code based algorithm for the closest pair problem, a new LCA for matrix inversion, lower bounds for testing triangle-freeness, and several structural results on Boolean functions with low Fourier sparsity. So far, there have been 4 conference papers and 2 journal papers have been produced under the support of this project, and we expect at least several more to come in the next one or two years.
Overall, the project provided substantive educational opportunities for 3 graduate students to pursue their PhD degrees. Among these three students, one is going to graduate in Fall 2018 (under the supervision of another faculty in PI's department), one is expected to graduate in Summer or Fall 2019, and the third student is making good progress under PI's supervision.
Last Modified: 10/29/2018
Modified by: Ning Xie
Please report errors in award information by writing to: awardsearch@nsf.gov.
