| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | July 18, 2008 |
| Latest Amendment Date: | August 18, 2009 |
| Award Number: | 0829672 |
| Award Instrument: | Continuing Grant |
| Program Manager: |
Dmitri Maslov
CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | September 1, 2008 |
| End Date: | August 31, 2013 (Estimated) |
| Total Intended Award Amount: | $450,000.00 |
| Total Awarded Amount to Date: | $450,000.00 |
| Funds Obligated to Date: |
FY 2009 = $150,000.00 |
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
77 MASSACHUSETTS AVE CAMBRIDGE MA US 02139-4301 (617)253-1000 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
77 MASSACHUSETTS AVE CAMBRIDGE MA US 02139-4301 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): |
Information Technology Researc, THEORY OF COMPUTING, Special Projects - CCF |
| Primary Program Source: |
01000910DB 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
This project initiates new, unifying directions in Property Testing.
Property Testing is the area of algorithmic research that attempts to discover global properties of data by by sampling the data probabilistically in very few places. The ``oldest'' property test might be the use of polling to predict the outcome of an upcoming election. Modern research has extended the scope of property tests to a much richer class of properties including tests of linearity (``is the data essentially linear with respect to some parameters"), multilinearity, low-degreeness, colorability (``is the data describing a graph with small chromatic number") etc.
The goal of this project is to shed light on the question: What makes some properties testable so efficiently, that we do not have to look at the entire data in order to test for it? The thesis underlying the project is that for interesting properties, testability ought to be related to the ``invariances" shown by the property: i.e., if the data is viewed as a function from some input to some output, then the ``invariances" are given by a set (a group) of permutations of the input space under which the property remains unchanged. The project explores a variety of potential invariances to consider and studies conditions under which {\em every} property exhibiting such invariance is testable.
The broader impact of the project is to find ways of coping with the data explosion problem faced by many computers, by describing settings where massive data may be analyzed by sampling small pieces.
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.
