48 citations · 48 across the 5 of their papers we have counts for
5 papers
Optimal chain density, entropy, and space-time tradeoffs for the TSP
Alexandr Andoni, Justin Dallant, László Kozma +1
We nearly settle a natural extremal question about set systems over : the tradeoff between the {size} (number of sets) and the number of {full chains}. This question was initi…
Statistical-Computational Trade-offs for Density Estimation
Anders Aamand, Alexandr Andoni, Justin Y. Chen +4
We study the density estimation problem defined as follows: given distributions over a discrete domain , as well as a collection of samples chosen from…
Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems
Josh Alman, Alexandr Andoni, Hengjie Zhang
We study the average-case version of the Orthogonal Vectors problem, in which one is given as input vectors from which are chosen randomly so that each coordinate i…
Sub-quadratic (1+\eps)-approximate Euclidean Spanners, with Applications
Alexandr Andoni, Hengjie Zhang
We study graph spanners for point-set in the high-dimensional Euclidean space. On the one hand, we prove that spanners with stretch <\sqrt{2} and subquadratic size are not possible…
Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors
Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn +1
[See the paper for the full abstract.] We show tight upper and lower bounds for time-space trade-offs for the -Approximate Near Neighbor Search problem. For the -dimensional…