Distortion Growth

NSF Award Search · 01002526DB NSF RESEARCH & RELATED ACTIVIT · $350,000 · view on nsf.gov ↗

Abstract

Understanding the structure of massive collections of objects in terms of pairwise distances among their members is fundamentally important to human activities and interests throughout science, industry, and beyond. Here, the notion of “distance” is varied and hence highly expressive: It can include familiar settings such as the 3-dimensional world in which we live and the geometry of curved surfaces, and it covers important notions of proximity within, for examples, social networks, collections of proteins or images, the Internet, and many more; such geometries typically reside in high dimensions and seem nonintuitive or strange in comparison to our Euclidean surroundings. A paradigm that has proven to be ubiquitously powerful and useful to a rich variety of pure and applied investigations is embedding a geometric space of interest into a “nicer” space in which one knows how to perform important tasks (e.g., discovering clusters, efficient storage, compression and optimization, and many more). Typically, this goal cannot be achieved without distorting distances, so the pertinent issue is determining the rate of growth of the smallest possible distortion. This is the overarching theme of the project, which is devoted to resolving central issues and longstanding mysteries of the field. For example, it is not even known how much distances must be distorted, in terms of the total number of objects, when one wishes to represent them in the 3-dimesnional space in which we reside.

Key facts

NSF award ID
2453936
Awardee
Princeton University (NJ)
SAM.gov UEI
NJ1YPQXQG7U5
PI
Assaf Naor
Primary program
01002526DB NSF RESEARCH & RELATED ACTIVIT
All programs
Artificial Intelligence (AI)
Estimated total
$350,000
Funds obligated
$350,000
Transaction type
Standard Grant
Period
07/01/2025 → 06/30/2028