- Home
- Research Areas
- Biological Sciences (BIO)
- Computer and Information Science and Engineering (CISE)
- Education and Human Resources (EHR)
- Engineering (ENG)
- Environmental Research and Education (ERE)
- Geosciences (GEO)
- Integrative Activities (OIA)
- International Science and Engineering (OISE)
- Mathematical and Physical Sciences (MPS)
- Social, Behavioral and Economic Sciences (SBE)
- Funding
- About Funding
- Archived Funding Search
- Due Dates
- Find Funding
- Merit Review
- Policies and Procedures
- Preparing Proposals
- Recent Opportunities
- Transformative Research
- Related Links
- Proposal and Award Policies and Procedures Guide (PAPPG)
- Research.gov
- FastLane
- Funding Opportunities For
- Graduate Students
- K-12 Educators
- Postdoctoral Fellows
- Undergraduate Students
- Small Business
- Awards
- Document Library
- News
- About NSF
Award Abstract # 1617713
AF: Small: Randomness in Computation - Old Problems and New Directions
| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Awardee: |
|
| Initial Amendment Date: | May 25, 2016 |
| Latest Amendment Date: | May 25, 2016 |
| Award Number: | 1617713 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Tracy Kimbrel
tkimbrel@nsf.gov (703)292-7924 CCF Division of Computing and Communication Foundations CSE Direct For Computer & Info Scie & Enginr |
| Start Date: | July 1, 2016 |
| End Date: | June 30, 2020 (Estimated) |
| Total Intended Award Amount: | $374,815.00 |
| Total Awarded Amount to Date: | $374,815.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Awardee Sponsored Research Office: |
1101 E 33rd St Baltimore MD US 21218-2686 (443)997-1898 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
3400 N CHARLES ST Baltimore MD US 21218-2608 |
| Primary Place of Performance Congressional District: |
|
| DUNS ID: |
|
| Parent DUNS ID: |
|
| 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
A major goal of computer science is to study how to compute more efficiently using limited resources. The understanding of this question has had profound influence on our daily life, in a variety of areas ranging from e-commerce, cloud computing, to travel planning and weather forecast. In this project the PI seeks to understand how to efficiently use the valuable resource of randomness (such as coin flips) in computation.
Randomness is extremely useful in computation and widely used in practice. Simulation of complex models such as those used for weather forecast and economy prediction relies on the use of random processes, and modern computer security will be lost completely without randomness. In this context, the project studies the fundamental questions of the power and limitations of randomness in computation. From a theoretical aspect, it can lead to breakthroughs towards solving long standing open questions in computer science, such as whether randomness is really necessary for algorithms. From a practical aspect, it can lead to improvements in several areas important to society, such as designing streaming and scalable computation protocols for massive datasets, enhancing computer security in an adversarial environment, and tolerating errors in communication protocols. Based on the research activities, the educational component in this project plans to train several Ph.D. students, publish online surveys for free access, integrate research outcomes into courses the PI is or will be teaching, and provide research opportunities for minority students through a joint effort with Johns Hopkins University.
The questions that will be addressed in this project include how to generate high quality randomness for computation, how to use randomness in the presence of information leakage or tampering by an adversary, and how to use randomness to detect and correct errors introduced in communications. Two fundamental objects and tools for studying these questions are pseudorandom generators and randomness extractors. A pseudorandom generator is an algorithm that stretches a small number of random bits into a large number of bits that appear to be perfectly random to a certain class of functions. A randomness extractor is an algorithm that converts low quality random sources into very high quality random bits. The project will explore new ways of constructing these objects, as well as the connections between these objects and other areas in computer science, such as cryptography, error correcting codes, and computational complexity. Through this the PI seeks to establish new connections between different areas, and thus leading to possible new breakthroughs.
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.
(Showing: 1 - 10 of 12)
Eshan Chattopadhyay, Xin Li
"Explicit Non-Malleable Extractors, Multi-Source Extractors and Almost Optimal Privacy Amplification Protocols"
57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
, 2016
Eshan Chattopadhyay, Xin Li
"Non-Malleable Codes and Extractors for Small-Depth Circuits, and Affine Functions"
49th Annual ACM Symposium on the Theory of Computing (STOC 2017)
, 2017
Xin Li
"Improved Two-Source Extractors, and Affine Extractors for Polylogarithmic Entropy"
57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2016)
, 2016
Xin Li
"Improved Non-Malleable Extractors, Non-Malleable Codes and Independent Source Extractors"
49th Annual ACM Symposium on the Theory of Computing (STOC 2017)
, 2017
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma
"A New Approach for Constructing Low-Error, Two-Source Extractors"
2018 Computational Complexity Conference (CCC 2018)
, 2018
Kuan Cheng, Yuval Ishai, Xin Li
"Near-Optimal Secret Sharing and Error Correcting Codes in AC0"
Fifteenth Theory of Cryptography Conference (TCC 2017)
, 2017
Kuan Cheng, Xin Li
"Randomness Extraction in AC0 and with Small Locality"
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
, 2018
Xin Li, Shachar Lovett, Jiapeng Zhang
"Sunflowers and Quasi-sunflowers from Randomness Extractors"
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
, 2018
Kuan Cheng, Zhengzhong Jin, Xin Li, Ke Wu
"Deterministic Document Exchange Protocols, and Almost Optimal Binary Codes for Edit Errors"
2018 IEEE Symposium on Foundations of Computer Science (FOCS 2018)
, 2018
Kuan Cheng, Bernhard Haeupler, Xin Li, Amirbehshad Shahrasbi, Ke Wu
"Synchronization Strings: Efficient and Fast Deterministic Constructions over Small Alphabets"
ACM-SIAM Symposium on Discrete Algorithms (SODA19)
, 2019
Eshan Chattopadhyay, Jesse Goodman, Vipul Goyal, Xin Li
"Extractors for Adversarial Sources via Extremal Hypergraphs"
52nd Annual ACM Symposium on Theory of Computing (STOC 2020)
, 2020
(Showing: 1 - 10 of 12)
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 use of randomness is prevalent in computer science, from achieving efficient algorithms to ensuring the security of cryptographic systems. This project studied the fundamental questions of the power and limitations of randomness (such as coin flips) in computation. Especially, a major goal is to understand the form of randomness which has enough quality to be used reliably in the extremely wide computing applications.
The major tool in studying the above question is randomness extractor, which is an algorithm that converts low quality random sources into very high quality random bits. This project has vastly advanced our knowledge of randomness extractors. Specifically, significant progress has been achieved towards long standing major open problems, resulting in near optimal constructions of randomness extractors for independent weak random sources, a model that has been studied for over 30 years since the beginning of this area. The project has also led to new and improved extractors for more general models beyond independent sources, such as random sources that are generated with limited resources, sources with limited dependence, and sources arising from bounded collusion leakage.
Another important outcome from this project is the significantly improved understanding of using randomness to achieve security. In this line, the project has led to vastly improved and near optimal constructions of privacy amplification protocols, solving a major open problem of 25 years; and non malleable error correcting codes which can handle a much broader class of attacks that can tamper with the entire codeword. The privacy amplification protocols are widely used in symmetric key cryptography, such as quantum key distribution; the non malleable codes provide extraordinary security protection for data storage.
A third major outcome falls in the direction of constructing error correcting codes for edit errors, which include insertions and deletions and happen frequently in practice. Such errors generalize standard symbol modifications and have been studied for decades since the beginning of information theory, yet without much progress on their corresponding codes. The project has led to substantial progress that achieved near optimal parameters in several different settings. This for the first time brings our understanding of codes for edit errors close to our understanding of codes for standard symbol modifications.
The results from this project have been summarized in more than 15 peer reviewed scientific papers, appearing in top theoretical computer science conferences such as Annual Symposium on Foundations of Computer Science (FOCS), Annual ACM Symposium on the Theory of Computing (STOC), ACM-SIAM Symposium on Discrete Algorithms (SODA), International Colloquium on Automata, Languages and Programming (ICALP) and International Cryptology Conference (Crypto).
Several results from this project have been integrated into the PI's classes, and disseminated through workshops and seminars. The project has supported three PhD students, all of whom have produced high quality research papers that have been published or are under review in top theoretical computer science conferences. The students have also had opportunities to give presentations at conferences and workshops, as well as giving lectures in the PI's classes. One student has graduated and obtained a tenure track assistant professor position in academia, with the other two on the right track towards their degrees.
Last Modified: 08/31/2020
Modified by: Xin Li
Please report errors in award information by writing to: awardsearch@nsf.gov.
