| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | September 11, 2017 |
| Latest Amendment Date: | September 11, 2017 |
| Award Number: | 1749750 |
| 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 15, 2017 |
| End Date: | August 31, 2018 (Estimated) |
| Total Intended Award Amount: | $125,000.00 |
| Total Awarded Amount to Date: | $125,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
1033 MASSACHUSETTS AVE STE 3 CAMBRIDGE MA US 02138-5366 (617)495-5501 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
33 Oxford Street Cambridge MA US 02138-2933 |
| 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
Pseudorandomness is the theory of generating objects that "look random" despite being constructed using little or no randomness. The computational theory of pseudorandomness originated in the foundations of cryptography in the early 1980s and has since developed into a rich subfield of theoretical computer science in its own right. The notions and constructs studied in the theory of pseudorandomness have implications for many different areas of research in computer science, communications, and mathematics.
This EArly-concept Grant for Exploratory Research (EAGER) project seeks to identify novel approaches to some of the most enduring and important challenges in pseudorandomness as well as opportunities for new applications of pseudorandomness. The research will be closely integrated with the PIs' educational efforts. In particular, the PIs will continue to develop new curricular, educational, and expository material that are made openly available for others to use. Graduate and undergraduate students will be involved in all phases of this research, and will be given opportunities to publish and present their results at premier international conferences. The PIs will also continue their extensive service to the scientific community.
Specifically, the project will try to uncover new approaches to topics such as:
1. The RL vs. L problem: trying to prove, unconditionally, that every randomized algorithm can be made deterministic with only a constant-factor loss in memory usage.
2. Cryptography: identifying optimally efficient constructions of cryptographic primitives from minimal assumptions.
3. Machine Learning: can pseudorandomness help in making machine learning robust to adversarial noise or to overfitting?
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.
Pseudorandomness is the theory of generating objects that "look random" despite being constructed using little or no randomness. The computational theory of pseudorandomness originated in the foundations of cryptography in the early 1980s and has since developed into a rich subfield of theoretical computer science in its own right. The notions and constructs studied in the theory of pseudorandomness have implications for many different areas of research in computer science, communications, and mathematics.
This Early-concept Grant for Exploratory Research (EAGER) project identified novel approaches to some of the most enduring and important challenges in pseudorandomness as well as opportunities for new applications of pseudorandomness. These include:
-
Developing a new technique related to the long-standing “RL vs. L problem” --- which asks whether every randomized algorithm can be made deterministic with only a constant-factor loss in memory usage.
-
Taking a significant step towards proving that known constructions of fundamental cryptographic primitives from minimal assumptions have optimal efficiency.
-
Providing a quantitatively tight bound on how much leaking a small amount of information about a secret can help an adversary attacking a cryptographic scheme.
The research was closely integrated with the PIs' educational efforts. The project provided research training to several PhD students, one undergraduate, and one postdoc. During the project, the PIs also developed and revised undergraduate courses in theoretical computer science.
Last Modified: 12/19/2018
Modified by: Salil P Vadhan
Please report errors in award information by writing to: awardsearch@nsf.gov.
