| NSF Org: |
CCF Division of Computing and Communication Foundations |
| Recipient: |
|
| Initial Amendment Date: | May 6, 2021 |
| Latest Amendment Date: | May 6, 2021 |
| Award Number: | 2104489 |
| Award Instrument: | Standard Grant |
| Program Manager: |
Phillip Regalia
pregalia@nsf.gov (703)292-2981 CCF Division of Computing and Communication Foundations CSE Directorate for Computer and Information Science and Engineering |
| Start Date: | July 1, 2021 |
| End Date: | June 30, 2024 (Estimated) |
| Total Intended Award Amount: | $500,000.00 |
| Total Awarded Amount to Date: | $500,000.00 |
| Funds Obligated to Date: |
|
| History of Investigator: |
|
| Recipient Sponsored Research Office: |
3112 LEE BUILDING COLLEGE PARK MD US 20742-5100 (301)405-6269 |
| Sponsor Congressional District: |
|
| Primary Place of Performance: |
2361 A.V. Williams College Park MD US 20742-1000 |
| Primary Place of
Performance Congressional District: |
|
| Unique Entity Identifier (UEI): |
|
| Parent UEI: |
|
| NSF Program(s): | Comm & Information 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
The project studies properties of sequences of zeros and ones formed of n bits. Collections of such sequences, called codes, are used for representing data to be stored in computer memory or transmitted over an optical cable. In many applications in communications, statistics, and computer science it is beneficial to choose a code that is in some ways uniformly distributed over the set of all the possible binary sequences. These applications have led researchers to define a large group of problems in applied mathematics both on the theory side and in the domain of data processing procedures. The main topic of this project is investigation of uniformly distributed codes, including their construction, evaluation of the properties, a group of related geometric problems, as well and their uses in applied problems of algorithm design, computer vision, and economical representation of data. The project relies on ideas drawn from recent developments in computer science as well as certain classical methods in applied mathematics, and it aims at new characterizations and applications of uniformly distributed sets of binary sequences.
The theory of uniform distributions has seen ongoing development through most of the last century, motivated primarily by problems of numerical integration of multivariable functions. In the context of point sets on the surface of the sphere in n dimensions, approximation to the uniform distribution is quantified by the quadratic discrepancy of the point set, measured as the average number of points of the set in a region of the surface of the sphere. Spherical point sets with small quadratic discrepancy approach uniformly distributed collections of points on the sphere. This project is devoted to an extension of this theory to binary codes that approximate the uniform distribution on the Hamming space. Ways of advancing the theory of such codes were suggested in recent works of the investigator, and they rely on Fourier analysis on the Boolean cube, the theory of positive-definite kernels, linear programming, and other tools from coding theory. Applications of this work include estimating the error probability of decoding, derandomization of algorithms, and some variants of the compressed sensing problem.
This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.
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.
In many problems of computer science and engineering, data is represented using binary bit strings. For the purposes of reliable communication or storage, these strings are often supplemented with parity checks, enabling the recovery of the data corrupted by noise. A range of problems in communication and cryptography further calls for the encoded vectors to be distributed uniformly in the space of all such vectors. This project studied properties and limitations of binary codes from the perspective of the uniform distribution.
One such group of problems relates to reliable transmission of the data over a public channel which at the same time should be protected from unauthorized actors seeking to acquire the transmitted information. If those actors observe a uniformly distributed data stream, they are unable to gain any knowledge of the protected information.
This project explored limitations of attainable rates of communication under the condition that the encoded data be close to the uniform distribution on the set of binary strings. Utilizing a range of measures of closeness, the project introduced new techniques to find such rates, and gave precise answers in a broad range of cases. The results established in the project rely on mathematical proofs that involve new tools within information and coding theory to complete the arguments. These results also connect the problem of uniform distributions with several previously unrelated methods in combinatorial mathematics and information theory, developing a deeper understanding of the methods and their applicability range.
The project has additionally explored applications of the methods developed in it in problems of computer science motivated by cryptographic applications. One of these problems, known as hashing, enters many cryptographic primitives underlying a wide range of secure communication applications such as financial transactions or data storage. The specific results obtained in the project design new tools to used to derive sharper guarantees for uniformity of the encoded data irrespective of the initial conditions for the source that generates it. They advance the state of the art in the problem of linear hashing and related tasks of applied cryptography.
The results of the project were broadly disseminated in the form of online preprints, published or submitted journal papers, and multiple talks at colloquia and conferences over the 3-year period. The project also supported Ph.D. research of a student who will graduate with a doctoral degree within the next academic year. Presentation of the results has led to new collaborations between the PI and his students and colleagues from other universities that will likely extend beyond the term of this project.
Last Modified: 08/31/2024
Modified by: Alexander Barg
Please report errors in award information by writing to: awardsearch@nsf.gov.
