More Like this

1. Higher-dimensional gap theorems for the maximum metric

   https://doi.org/10.1142/S1793042121500548  

   Haynes, Alan; Ramirez, Juan J. (February 2021, International Journal of Number Theory)

   null (Ed.)

   Recently, the first author together with Jens Marklof studied generalizations of the classical three distance theorem to higher-dimensional toral rotations, giving upper bounds in all dimensions for the corresponding numbers of distances with respect to any flat Riemannian metric. In dimension two they proved a five distance theorem, which is best possible. In this paper, we establish analogous bounds, in all dimensions, for the maximum metric. We also show that in dimensions two and three our bounds are best possible. 

   more » « less
2. Distinct Angles and Angle Chains in Three Dimensions

   https://doi.org/10.46298/dmtcs.10037  

   Ascoli, Ruben; Betti, Livia; Duke, Jacob Lehmann; Liu, Xuyan; Milgrim, Wyatt; Miller, Steven J.; Palsson, Eyvindur A.; Acosta, Francisco Romero; Iannuzzelli, Santiago Velazquez (February 2023, Discrete Mathematics & Theoretical Computer Science)

   In 1946, Erd\H{o}s posed the distinct distance problem, which seeks to findthe minimum number of distinct distances between pairs of points selected fromany configuration of $$n$$ points in the plane. The problem has since beenexplored along with many variants, including ones that extend it into higherdimensions. Less studied but no less intriguing is Erd\H{o}s' distinct angleproblem, which seeks to find point configurations in the plane that minimizethe number of distinct angles. In their recent paper "Distinct Angles inGeneral Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolfuse a logarithmic spiral to establish an upper bound of $$O(n^2)$ on the minimumnumber of distinct angles in the plane in general position, which prohibitsthree points on any line or four on any circle. We consider the question of distinct angles in three dimensions and providebounds on the minimum number of distinct angles in general position in thissetting. We focus on pinned variants of the question, and we examine explicitconstructions of point configurations in $$\mathbb{R}^3$$ which useself-similarity to minimize the number of distinct angles. Furthermore, westudy a variant of the distinct angles question regarding distinct angle chainsand provide bounds on the minimum number of distinct chains in $$\mathbb{R}^2$$and $$\mathbb{R}^3$$. 

   more » « less
3. Approximate Nearest Neighbors in Limited Space

   https://doi.org/10.1137/1.9781611975031  

   Indyk, Piotr; Wagner, Tal (January 2018, Conference on Learning Theory)

   We consider the (1+ϵ)-approximate nearest neighbor search problem: given a set X of n points in a d-dimensional space, build a data structure that, given any query point y, finds a point x∈X whose distance to y is at most (1+ϵ)minx∈X ‖x−y‖ for an accuracy parameter ϵ∈(0,1). Our main result is a data structure that occupies only O(ϵ^−2 n log(n)log(1/ϵ)) bits of space, assuming all point coordinates are integers in the range {−n^O(1)…n^O(1)}, i.e., the coordinates have O(logn) bits of precision. This improves over the best previously known space bound of O(ϵ^−2 n log(n)^2), obtained via the randomized dimensionality reduction method of Johnson and Lindenstrauss (1984). We also consider the more general problem of estimating all distances from a collection of query points to all data points X, and provide almost tight upper and lower bounds for the space complexity of this problem. 

   more » « less
4. Navigable Graphs for High-Dimensional Nearest Neighbor Search: Constructions and Limits

   Diwan, Haya; Gou, Jinrui; Musco, Cameron; Musco, Christopher; Suel, Torsten (December 2024, Advances in Neural Information Processing Systems)

   There has been significant recent interest in \emph{graph-based nearest neighbor search methods}, many of which are centered on the construction of (approximately) {\em navigable}\/ graphs over high-dimensional point sets. A graph is navigable if we can successfully move from any starting node to any target node using a greedy routing strategy where we always move to the neighbor that is closest to the destination according to the given distance function. The complete graph is obviously navigable for any point set, but the important question for applications is if sparser graphs can be constructed. While this question is fairly well understood in low-dimensions, we establish some of the first upper and lower bounds for high-dimensional point sets. First, we give a simple and efficient way to construct a navigable graph with average degree $$O(\sqrt{n \log n })$$ for any set of $$n$$ points, in any dimension, for any distance function. We compliment this result with a nearly matching lower bound: even under the Euclidean metric in $$O(\log n)$$ dimensions, a random point set has no navigable graph with average degree $$O(n^{\alpha})$$ for any $$\alpha < 1/2$$. Our lower bound relies on sharp anti-concentration bounds for binomial random variables, which we use to show that the near-neighborhoods of a set of random points do not overlap significantly, forcing any navigable graph to have many edges. 

   more » « less
5. Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions

   Chen, Justin Y; Indyk, Piotr; Woodruff, David P (July 2024, Innovations in Theoretical Computer Science)

   Metric embeddings traditionally study how to map n items to a target metric space such that distance lengths are not heavily distorted. However, what if we are only interested in preserving the relative order of the distances, rather than their exact lengths? In this paper, we explore the fundamental question: given triplet comparisons of the form “item i is closer to item j than to item k,” can we find low-dimensional Euclidean representations for the n items that respect those distance comparisons? Such order-preserving embeddings naturally arise in important applications—such as recommendations, ranking, crowdsourcing, psychometrics, and nearest-neighbor search—and have been studied since the 1950s under the name of ordinal or non-metric embeddings. Our main results include: Nearly-Tight Bounds on Triplet Dimension: We introduce the concept of triplet dimension of a dataset and show, surprisingly, that in order for an ordinal embedding to be triplet-preserving, its dimension needs to grow as n^2 in the worst case. This is nearly optimal, as n−1 dimensions always suffice. Tradeoffs for Dimension vs (Ordinal) Relaxation: We relax the requirement that every triplet must be exactly preserved and present almost tight lower bounds for the maximum ratio between distances whose relative order was inverted by the embedding. This ratio is known as (ordinal) relaxation in the literature and serves as a counterpart to (metric) distortion. New Bounds on Terminal and Top-k-NNs Embeddings: Moving beyond triplets, we study two well-motivated scenarios where we care about preserving specific sets of distances (not necessarily triplets). The first scenario is Terminal Ordinal Embeddings where we aim to preserve relative distance orders to k given items (the “terminals”), and for that, we present matching upper and lower bounds. The second scenario is top-k-NNs Ordinal Embeddings, where for each item we aim to preserve the relative order of its k nearest neighbors, for which we present lower bounds. To the best of our knowledge, these are some of the first tradeoffs on triplet-preserving ordinal embeddings and the first study of Terminal and Top-k-NNs Ordinal Embeddings. 

   more » « less