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 $n$ vectors from $\{0,1{\}}^d$ which are chosen randomly so that each coordinate i…