3 papers
cs.DS2024
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…
cs.DS2023
Generalizations of Matrix Multiplication can solve the Light Bulb Problem
Josh Alman, Hengjie Zhang
In the light bulb problem, one is given uniformly random vectors . They are all chosen independently except a planted pair $(x_{i…
cs.CG2023
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…